The Bose-Hubbard Model is QMA-complete
Open accessThe DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.
Abstract
The Bose-Hubbard model is a system of interacting bosons that live on the vertices of a graph. The particles can move between adjacent vertices and experience a repulsive on-site interaction. The Hamiltonian is determined by a choice of graph that specifies the geometry in which the particles move and interact. We prove that approximating the ground energy of the Bose-Hubbard model on a graph at fixed particle number is QMA-complete. In our QMA-hardness proof, we encode the history of an n-qubit computation in the subspace with at most one particle per site (i.e., hard-core bosons). This feature, along with the well-known mapping between hard-core bosons and spin systems, lets us prove a related result for a class of 2-local Hamiltonians defined by graphs that generalizes the XY model. By avoiding the use of perturbation theory in our analysis, we circumvent the need to multiply terms in the Hamiltonian by large coefficients.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Feynman, R. P. (1985) · Optics News · doi:10.1364/on.11.2.000011 · Cited by 1,023
The Complexity of the Local Hamiltonian Problem
Kempe, J., Kitaev, A., & Regev, O. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704445226 · Cited by 648
Universal Computation by Multiparticle Quantum Walk
Childs, A. M., Gosset, D., & Webb, Z. (2013) · Science · doi:10.1126/science.1229957 · Cited by 456 · cited 10×
“Recently we showed that the Bose-Hubbard model on a graph can perform efficient universal quantum computation [8].”
BackgroundMethodInfluentialSelf-citationSchuch, N., & Verstraete, F. (2009) · Nature Physics · doi:10.1038/nphys1370 · Cited by 260 · cited 1×
“There are also frustration-free states where two of the three particles are located in the same two-qubit gadget J ∈ [M ] and one of the particles is located in a diagram element L1 from a different component of the graph.”
BackgroundQuantum Computational Complexity of the N -Representability Problem: QMA Complete
Liu, Y.-K., Christandl, M., & Verstraete, F. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.110503 · Cited by 211 · cited 1×
“By applying such mappings to the Local Hamiltonian problem, one can show that certain bosonic [30] and fermionic [23] Hamiltonian problems are QMA-hard.”
MethodEfficient algorithm for a quantum analogue of 2-SAT
Bravyi, S. (2011) · Contemporary Mathematics · doi:10.1090/conm/536/10552 · Cited by 98 · cited 24×
“Also note that I (Gi, G X , n) = I (GX , G X , n) for i ∈ [4] since the gate diagrams for each of the graphs G1, G2, G3, G4 and GX have the same set of diagram elements.”
BackgroundInfluentialBookatz, A. D. (2014) · Quantum Information and Computation · doi:10.26421/qic14.5-6-1 · Cited by 26
Cited by
Quantum Chemistry in the Age of Quantum Computing
Cao, Y., Romero, J., Olson, J. P., Degroote, M., Johnson, P. D., Kieferová, M., Kivlichan, I. D., Menke, T., Peropadre, B., Sawaya, N. P. D., et al. (2019) · Chemical Reviews · doi:10.1021/acs.chemrev.8b00803 · Cited by 1,560
Adiabatic Quantum Simulation of Quantum Chemistry
Babbush, R., Love, P. J., & Aspuru-Guzik, A. (2014) · Scientific Reports · doi:10.1038/srep06603 · Cited by 191
Exploiting Locality in Quantum Computation for Quantum Chemistry
McClean, J. R., Babbush, R., Love, P. J., & Aspuru-Guzik, A. (2014) · The Journal of Physical Chemistry Letters · doi:10.1021/jz501649m · Cited by 125
Dallaire-Demers, P.-L., & Wilhelm, F. K. (2016) · Physical Review A · doi:10.1103/physreva.93.032303 · Cited by 31
Metadata
- Authors
- Childs, A. M., Gosset, D., & Webb, Z.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2014
- Pages
- 308-319
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W2944028372
- Cited by
- 18
- References
- 7
- FWCI
- 1.38
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: The Bose-Hubbard Model is QMA-complete. https://app.cochat.ai/papers/10.1007/978-3-662-43948-7_26
- The paper
- Childs, A. M., Gosset, D., & Webb, Z. (2014). The Bose-Hubbard Model is QMA-complete. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-662-43948-7_26
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.