Quantum Hamiltonian Complexity
Open accessThe DOI matches its Crossref record; 194 of the 209 references it cites were found in a registry or an index, and 15 are not checked yet.
Abstract
Constraint satisfaction problems are a central pillar of modern computational complexity theory. This survey provides an introduction to the rapidly growing field of Quantum Hamiltonian Complexity, which includes the study of quantum constraint satisfaction problems. Over the past decade and a half, this field has witnessed fundamental breakthroughs, ranging from the establishment of a “Quantum Cook-Levin Theorem” to deep insights into the structure of 1D low-temperature quantum systems via so-called area laws. Our aim here is to provide a computer science-oriented introduction to the subject in order to help bridge the language barrier between computer scientists and physicists in the field. As such, we include the following in this survey: (1) The motivations and history of the field, (2) a glossary of condensed matter physics terms explained in computer-science friendly language, (3) overviews of central ideas from condensed matter physics, such as indistinguishable particles, mean field theory, tensor networks, and area laws, and (4) brief expositions of selected computer science-based results in the area. For example, as part of the latter, we provide a novel information theoretic presentation of Bravyi’s polynomial time algorithm for Quantum 2-SAT.
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.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“This modification of the optical apparatus stems from the unitary transformation (Equation 19) that encodes the molecular problem 220 .”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [220]
Experimental — accuracy not yet measured
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
Quantum Computation and Quantum Information
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895
Quantum computation and quantum information
Law, J. (2001) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/505482.505499 · Cited by 18,842
Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables
W., J. W., Abramowitz, M., & Stegun, I. A. (1965) · Mathematics of Computation · doi:10.2307/2004114 · Cited by 18,663
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
Density matrix formulation for quantum renormalization groups
White, S. R. (1992) · Physical Review Letters · doi:10.1103/physrevlett.69.2863 · Cited by 7,702
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
Bekenstein, J. D. (1973) · Physical Review D · doi:10.1103/physrevd.7.2333 · Cited by 7,555
Fault-tolerant quantum computation by anyons
Kitaev, A. Y. (2003) · Annals of Physics · doi:10.1016/s0003-4916(02)00018-0 · Cited by 7,238
Electron correlations in narrow energy bands
Hubbard, J. (1963) · Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences · doi:10.1098/rspa.1963.0204 · Cited by 6,699
Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
Onsager, L. (1944) · Physical Review · doi:10.1103/physrev.65.117 · Cited by 6,510
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385
The density-matrix renormalization group in the age of matrix product states
Schollwöck, U. (2011) · Annals of Physics · doi:10.1016/j.aop.2010.09.012 · Cited by 4,818
The renormalization group: Critical phenomena and the Kondo problem
Wilson, K. G. (1975) · Reviews of Modern Physics · doi:10.1103/revmodphys.47.773 · Cited by 4,522
Two soluble models of an antiferromagnetic chain
Lieb, E., Schultz, T., & Mattis, D. (1961) · Annals of Physics · doi:10.1016/0003-4916(61)90115-4 · Cited by 4,280
Feynman, R. P. (1939) · Physical Review · doi:10.1103/physrev.56.340 · Cited by 3,857
The Approximation of One Matrix by Another of Lower Rank
Eckart, C., & Young, G. (1936) · Psychometrika · doi:10.1007/bf02288367 · Cited by 3,800
Zur Theorie der Metalle: I. Eigenwerte und Eigenfunktionen der linearen Atomkette
Bethe, H. (1931) · Zeitschrift f�r Physik · doi:10.1007/bf01341708 · Cited by 3,768
Haldane, F. D. M. (1983) · Physical Review Letters · doi:10.1103/physrevlett.50.1153 · Cited by 3,695
Die gegenw�rtige Situation in der Quantenmechanik
Schr�dinger, E. (1935) · Die Naturwissenschaften · doi:10.1007/bf01491891 · Cited by 3,392 · cited 1×
“) Entanglement is one of the key characteristics distinguishing the quantum world from the classical one [143], and is in fact a necessary resource for (pure state) quantum computation to exponentially outperform classical computation [98].”
BackgroundThe density-matrix renormalization group
Schollwöck, U. (2005) · Reviews of Modern Physics · doi:10.1103/revmodphys.77.259 · Cited by 3,323
Entanglement entropy and quantum field theory
Calabrese, P., & Cardy, J. (2004) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2004/06/p06002 · Cited by 3,275
Entanglement Entropy and Quantum Field Theory
Calabrese, P., & Cardy, J. (2004) · arXiv · doi:10.48550/arxiv.hep-th/0405152 · Cited by 3,275
Density-matrix algorithms for quantum renormalization groups
White, S. R. (1993) · Physical Review B · doi:10.1103/physrevb.48.10345 · Cited by 3,244
Absence of Mott Transition in an Exact Solution of the Short-Range, One-Band Model in One Dimension
Lieb, E. H., & Wu, F. Y. (1968) · Physical Review Letters · doi:10.1103/physrevlett.20.1445 · Cited by 2,946
Haldane, F. D. M. (1983) · Physics Letters A · doi:10.1016/0375-9601(83)90631-x · Cited by 2,883
Colloquium : Area laws for the entanglement entropy
Eisert, J., Cramer, M., & Plenio, M. B. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.277 · Cited by 2,873
Sachdev, S. (2011) · doi:10.1017/cbo9780511973765 · Cited by 2,842
Entanglement in Quantum Critical Phenomena
Vidal, G., Latorre, J. I., Rico, E., & Kitaev, A. (2003) · Physical Review Letters · doi:10.1103/physrevlett.90.227902 · Cited by 2,793
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · Cited by 2,376
Efficient Classical Simulation of Slightly Entangled Quantum Computations
Vidal, G. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.147902 · Cited by 2,368
Wilson, K. G. (1971) · Physical Review B · doi:10.1103/physrevb.4.3174 · Cited by 2,334
Rigorous results on valence-bond ground states in antiferromagnets
Affleck, I., Kennedy, T., Lieb, E. H., & Tasaki, H. (1987) · Physical Review Letters · doi:10.1103/physrevlett.59.799 · Cited by 2,223
Srednicki, M. (1993) · Physical Review Letters · doi:10.1103/physrevlett.71.666 · Cited by 1,858 · cited 1×
“In fact, the original interest in area laws in quantum systems also sprang from this intriguing analogy, in connection with the conjecture that the origin of the black hole entropy is the quantum entanglement between the inside and outside of the black hole [28, 34, 151].”
BackgroundStatistics of the Two-Dimensional Ferromagnet. Part I
Kramers, H. A., & Wannier, G. H. (1941) · Physical Review · doi:10.1103/physrev.60.252 · Cited by 1,812
Efficient Simulation of One-Dimensional Quantum Many-Body Systems
Vidal, G. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.040502 · Cited by 1,779 · cited 3×
“They have been used in the last decade, for example, by Vidal [157, 158] to efficiently classically simulate “slightly entangled” quantum computation (or quantum evolution).”
MethodVerstraete, F., Murg, V., & Cirac, J. I. (2008) · Advances in Physics · doi:10.1080/14789940801912366 · Cited by 1,762
The complexity of satisfiability problems
Schaefer, T. J. (1978) · Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 · doi:10.1145/800133.804350 · Cited by 1,737
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · doi:10.1017/cbo9780511804090 · Cited by 1,690
Entanglement entropy and conformal field theory
Calabrese, P., & Cardy, J. (2009) · Journal of Physics A: Mathematical and Theoretical · doi:10.1088/1751-8113/42/50/504005 · Cited by 1,688 · cited 1×
“In conformally invariant critical (gapless) systems, the area law is slightly violated with a logarithmic factor ∼ logn [47, 48], suggesting that MPS is still a fairly efficient parametrization.”
BackgroundThe one-dimensional Ising model with a transverse field
Pfeuty, P. (1970) · Annals of Physics · doi:10.1016/0003-4916(70)90270-8 · Cited by 1,688
Critical Exponents in 3.99 Dimensions
Wilson, K. G., & Fisher, M. E. (1972) · Physical Review Letters · doi:10.1103/physrevlett.28.240 · Cited by 1,655
Valence bond ground states in isotropic quantum antiferromagnets
Affleck, I., Kennedy, T., Lieb, E. H., & Tasaki, H. (1988) · Communications in Mathematical Physics · doi:10.1007/bf01218021 · Cited by 1,477
Quantum source of entropy for black holes
Bombelli, L., Koul, R. K., Lee, J., & Sorkin, R. D. (1986) · Physical Review D · doi:10.1103/physrevd.34.373 · Cited by 1,439 · cited 1×
“In fact, the original interest in area laws in quantum systems also sprang from this intriguing analogy, in connection with the conjecture that the origin of the black hole entropy is the quantum entanglement between the inside and outside of the black hole [28, 34, 151].”
BackgroundFinitely correlated states on quantum spin chains
Fannes, M., Nachtergaele, B., & Werner, R. F. (1992) · Communications in Mathematical Physics · doi:10.1007/bf02099178 · Cited by 1,422
Renormalization Group and Critical Phenomena. II. Phase-Space Cell Analysis of Critical Behavior
Wilson, K. G. (1971) · Physical Review B · doi:10.1103/physrevb.4.3184 · Cited by 1,414
Proof verification and the hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998) · Journal of the ACM · doi:10.1145/278298.278306 · Cited by 1,413
Classical and Quantum Computation
Kitaev, A., Shen, A., & Vyalyi, M. (2002) · Graduate Studies in Mathematics · doi:10.1090/gsm/047 · Cited by 1,387
On the computational complexity of Ising spin glass models
Barahona, F. (1982) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/15/10/028 · Cited by 1,306
Introduction to Quantum Mechanics
Griffiths, D. J., & Schroeter, D. F. (2018) · Cambridge University Press eBooks · doi:10.1017/9781316995433 · Cited by 1,258
Benioff, P. (1980) · Journal of Statistical Physics · doi:10.1007/bf01011339 · Cited by 1,244 · cited 1×
“ρ ∈ D(C2n)! This was essentially the reason why Richard Feynman originally proposed [66, 67] the concept of quantum computing (see also Benioff [29, 30, 31]) — he believed quantum computers might enable an efficient study of quantum systems (which is otherwise generally intractable on a classical computer).”
BackgroundOnset of Fermi Degeneracy in a Trapped Atomic Gas
DeMarco, B., & Jin, D. S. (1999) · Science · doi:10.1126/science.285.5434.1703 · Cited by 1,241
Probabilistic checking of proofs: a new characterization of NP
Arora, S., & Safra, S. (1998) · Journal of the ACM · doi:10.1145/273865.273901 · Cited by 1,153
An area law for one-dimensional quantum systems
Hastings, M. B. (2007) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2007/08/p08024 · Cited by 1,131
Vidal, G. (2007) · Physical Review Letters · doi:10.1103/physrevlett.99.220405 · Cited by 1,122
Yang, C. N., & Yang, C. P. (1966) · Physical Review · doi:10.1103/physrev.150.321 · Cited by 1,097
Thermodynamic limit of density matrix renormalization.
Östlund, S., & Rommer, S. (1995) · Physical Review Letters · doi:10.1103/physrevlett.75.3537 · Cited by 1,077
On the Complexity of Timetable and Multicommodity Flow Problems
Even, S., Itai, A., & Shamir, A. (1976) · SIAM Journal on Computing · doi:10.1137/0205048 · Cited by 1,057
A Mott insulator of fermionic atoms in an optical lattice
Jördens, R., Strohmaier, N., Günter, K., Moritz, H., & Esslinger, T. (2008) · Nature · doi:10.1038/nature07244 · Cited by 1,038
Feynman, R. P. (1985) · Optics News · doi:10.1364/on.11.2.000011 · Cited by 1,023
Tensor-entanglement-filtering renormalization approach and symmetry-protected topological order
Gu, Z.-C., & Wen, X.-G. (2009) · Physical Review B · doi:10.1103/physrevb.80.155131 · Cited by 1,002
Rigorous Results on Valence-Bond Ground States in Antiferromagnets
Affleck, I., Kennedy, T., Lieb, E. H., & Tasaki, H. (2004) · Condensed Matter Physics and Exactly Soluble Models · doi:10.1007/978-3-662-06390-3_18 · Cited by 989
Two-Dimensional Ising Model as a Soluble Problem of Many Fermions
SCHULTZ, T. D., MATTIS, D. C., & LIEB, E. H. (1964) · Reviews of Modern Physics · doi:10.1103/revmodphys.36.856 · Cited by 936
A linear-time algorithm for testing the truth of certain quantified boolean formulas
Aspvall, B., Plass, M. F., & Tarjan, R. E. (1979) · Information Processing Letters · doi:10.1016/0020-0190(79)90002-4 · Cited by 892
Goals and opportunities in quantum simulation
Cirac, J. I., & Zoller, P. (2012) · Nature Physics · doi:10.1038/nphys2275 · Cited by 891 · cited 1×
“Thus, the goal of quantum simulations may be easier to achieve than a large scale quantum computer [52].”
BackgroundTheory of Quantum Error Correction for General Noise
Knill, E., Laflamme, R., & Viola, L. (2000) · Physical Review Letters · doi:10.1103/physrevlett.84.2525 · Cited by 866
Symmetry protection of topological phases in one-dimensional quantum spin systems
Pollmann, F., Berg, E., Turner, A. M., & Oshikawa, M. (2012) · Physical Review B · doi:10.1103/physrevb.85.075125 · Cited by 848
Class of Quantum Many-Body States That Can Be Efficiently Simulated
Vidal, G. (2008) · Physical Review Letters · doi:10.1103/physrevlett.101.110501 · Cited by 847
On the role of entanglement in quantum-computational speed-up
Jozsa, R., & Linden, N. (2003) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2002.1097 · Cited by 839
Continuous Variable Quantum Information: Gaussian States and Beyond
Adesso, G., Ragy, S., & Lee, A. R. (2014) · Open Systems & Information Dynamics · doi:10.1142/s1230161214400010 · Cited by 787
Yang, C. N., & Yang, C. P. (1966) · Physical Review · doi:10.1103/physrev.150.327 · Cited by 732
Simulating Physics with Computers
Feynman, R. P. (2018) · Feynman and Computation · doi:10.1201/9780429500459-11 · Cited by 731
Matrix product states represent ground states faithfully
Verstraete, F., & Cirac, J. I. (2006) · Physical Review B · doi:10.1103/physrevb.73.094423 · Cited by 730
Metallic and Insulating Phases of Repulsively Interacting Fermions in a 3D Optical Lattice
Schneider, U., Hackermüller, L., Will, S., Best, T., Bloch, I., Costi, T. A., Helmes, R. W., Rasch, D., & Rosch, A. (2008) · Science · doi:10.1126/science.1165449 · Cited by 720
An Introduction to Quantum Computing
Kaye, P., Laflamme, R., & Mosca, M. (2006) · Oxford University Press eBooks · doi:10.1093/oso/9780198570004.001.0001 · Cited by 714
Area Laws in Quantum Systems: Mutual Information and Correlations
Wolf, M. M., Verstraete, F., Hastings, M. B., & Cirac, J. I. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.070502 · Cited by 696
Lieb-Schultz-Mattis in higher dimensions
Hastings, M. B. (2004) · Physical Review B · doi:10.1103/physrevb.69.104431 · Cited by 685
Sachdev, S. (2007) · Handbook of Magnetism and Advanced Magnetic Materials · doi:10.1002/9780470022184.hmm108 · Cited by 681
Dynamics of a Quantum Phase Transition: Exact Solution of the Quantum Ising Model
Dziarmaga, J. (2005) · Physical Review Letters · doi:10.1103/physrevlett.95.245701 · Cited by 672
Feynman-Graph Expansion for Critical Exponents
Wilson, K. G. (1972) · Physical Review Letters · doi:10.1103/physrevlett.28.548 · Cited by 655
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
Quantum mechanical evolution towards thermal equilibrium
Linden, N., Popescu, S., Short, A. J., & Winter, A. (2009) · Physical Review E · doi:10.1103/physreve.79.061103 · Cited by 625
Verstraete, F., Porras, D., & Cirac, J. I. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.227205 · Cited by 581
Bekenstein, J. D. (2019) · Jacob Bekenstein · doi:10.1142/9789811203961_0023 · Cited by 579
Matrix product state representations
Perez-Garcia, D., Verstraete, F., Wolf, M. M., & Cirac, J. I. (2007) · Quantum Information and Computation · doi:10.26421/qic7.5-6-1 · Cited by 568
Matrix Product State Representations
Perez-Garcia, D., Verstraete, F., Wolf, M., & Cirac, J. I. (2006) · Ghent University Academic Bibliography (Ghent University) · Cited by 565
Polynomial-Time Approximation Algorithms for the Ising Model
Jerrum, M., & Sinclair, A. (1993) · SIAM Journal on Computing · doi:10.1137/0222066 · Cited by 548
Hidden quantum nonlocality revealed by local filters
Gisin, N. (1996) · Physics Letters A · doi:10.1016/s0375-9601(96)80001-6 · Cited by 531 · cited 3×
“In contrast, we give a different description of the algorithm in terms of local filters [Gis96] from entanglement theory, which, in our opinion, is arguably more accessible to the quantum computing community.”
BackgroundMethodInfluentialThe statistical mechanics of lattice gases
Simon, B. (1993) · Cited by 512
The PCP theorem by gap amplification
Dinur, I. (2006) · Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing · doi:10.1145/1132516.1132553 · Cited by 501
Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
Verstraete, F., & Cirac, J. I. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.cond-mat/0407066 · Cited by 475
Violation of the Entropic Area Law for Fermions
Wolf, M. M. (2006) · Physical Review Letters · doi:10.1103/physrevlett.96.010404 · Cited by 475
Classical deterministic complexity of Edmonds' Problem and quantum entanglement
Gurvits, L. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780545 · Cited by 448
Renard, J. P., Verdaguer, M., Regnault, L. P., Erkelens, W. A. C., Rossat-Mignod, J., & Stirling, W. G. (1987) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/3/8/013 · Cited by 439
Experimental evidence for the Haldane gap in a spin-1 nearly isotropic, antiferromagnetic chain
Buyers, W. J. L., Morra, R. M., Armstrong, R. L., Hogan, M. J., Gerlach, P., & Hirakawa, A. K. (1986) · Physical Review Letters · doi:10.1103/physrevlett.56.371 · Cited by 434
Rommer, S., & Östlund, S. (1997) · Physical Review B · doi:10.1103/physrevb.55.2164 · Cited by 431
On the complexity of time table and multi-commodity flow problems
Even, S., Itai, A., & Shamir, A. (1975) · 16th Annual Symposium on Foundations of Computer Science (sfcs 1975) · doi:10.1109/sfcs.1975.21 · Cited by 431
Entropy Scaling and Simulability by Matrix Product States
Schuch, N., Wolf, M. M., Verstraete, F., & Cirac, J. I. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.030504 · Cited by 409
A proof of part of Haldane's conjecture on spin chains
Affleck, I., & Lieb, E. H. (1986) · Letters in Mathematical Physics · doi:10.1007/bf00400304 · Cited by 404
Quantum mechanical Hamiltonian models of Turing machines
Benioff, P. (1982) · Journal of Statistical Physics · doi:10.1007/bf01342185 · Cited by 402
Quantum information with Gaussian states
WANG, X., HIROSHIMA, T., TOMITA, A., & HAYASHI, M. (2007) · Physics Reports · doi:10.1016/j.physrep.2007.04.005 · Cited by 392
Renormalization and tensor product states in spin chains and lattices
Cirac, J. I., & Verstraete, F. (2009) · Journal of Physics A: Mathematical and Theoretical · doi:10.1088/1751-8113/42/50/504004 · Cited by 380
The complexity of quantum spin systems on a two-dimensional square lattice
Oliveira, R. I., & Terhal, B. M. (2008) · Quantum Information and Computation · doi:10.26421/qic8.10-2 · Cited by 362
Aspects of Generic Entanglement
Hayden, P., Leung, D. W., & Winter, A. (2006) · Communications in Mathematical Physics · doi:10.1007/s00220-006-1535-6 · Cited by 359
Computational complexity of projected entangled pair states
Schuch, N., Wolf, M. M., Verstraete, F., & Cirac, J. I. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.140506 · Cited by 313
Statistics of the Two-Dimensional Ferromagnet. Part II
Kramers, H. A., & Wannier, G. H. (1941) · Physical Review · doi:10.1103/physrev.60.263 · Cited by 310
Ground State of Liquid Helium-4 and Helium-3
Schiff, D., & Verlet, L. (1967) · Physical Review · doi:10.1103/physrev.160.208 · Cited by 307
Quantum Mechanical Models of Turing Machines That Dissipate No Energy
Benioff, P. (1982) · Physical Review Letters · doi:10.1103/physrevlett.48.1581 · Cited by 295
Real-space quantum renormalization groups
White, S. R., & Noack, R. M. (1992) · Physical Review Letters · doi:10.1103/physrevlett.68.3487 · Cited by 289
The complexity of stoquastic local Hamiltonian problems
Bravyi, S. B., Divincenzo, D. P., Oliveira, R. I., & Terhal, B. M. (2008) · Quantum Information and Computation · doi:10.26421/qic8.5-1 · Cited by 284
Entanglement in the XY spin chain
Its, A. R., Jin, B.-Q., & Korepin, V. E. (2005) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/38/13/011 · Cited by 280
Probabilistic checking of proofs; a new characterization of NP
Arora, S., & Safra, S. (1992) · Proceedings., 33rd Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267824 · Cited by 275
Schuch, N., & Verstraete, F. (2009) · Nature Physics · doi:10.1038/nphys1370 · Cited by 260
Marriott, C., & Watrous, J. (2005) · computational complexity · doi:10.1007/s00037-005-0194-x · Cited by 241
Solving gapped Hamiltonians locally
Hastings, M. B. (2006) · Physical Review B · doi:10.1103/physrevb.73.085115 · Cited by 239
Aspects of generic entanglement
Hayden, P. M., Leung, D., & Winter, A. (2004) · Explore Bristol Research · Cited by 236
Strong NP-hardness of the quantum separability problem
Gharibian, S. (2010) · Quantum Information and Computation · doi:10.26421/qic10.3-4-11 · Cited by 234
Self-citationBatrouni, G. G., & Scalettar, R. T. (2011) · Ultracold Gases and Quantum Information · doi:10.1093/acprof:oso/9780199603657.003.0007 · Cited by 221
Renormalization and tensor product states in spin chains and lattices
Cirac, J. I., & Verstraete, F. (2009) · MPG.PuRe (Max Planck Society) · Cited by 217
A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians
Landau, Z. A., Vazirani, U. V., & Vidick, T. (2015) · Nature Physics · doi:10.1038/nphys3345 · Cited by 216
Self-citationQuantum 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×
“Approximating the ground state energy of Hamiltonians acting on indistinguishable particles is also QMA-hard, as shown by Liu, Christandl and Verstraete for fermions [115] and Wei, Mosca, and Nayak for bosons [166].”
MethodThe Power of Quantum Systems on a Line
Aharonov, D., Gottesman, D., Irani, S., & Kempe, J. (2009) · Communications in Mathematical Physics · doi:10.1007/s00220-008-0710-3 · Cited by 210
A Proof of Part of Haldane’s Conjecture on Spin Chains
Affleck, I., & Lieb, E. H. (1986) · Condensed Matter Physics and Exactly Soluble Models · doi:10.1007/978-3-662-06390-3_17 · Cited by 198
Variational matrix-product-state approach to quantum impurity models
Weichselbaum, A., Verstraete, F., Schollwöck, U., Cirac, J. I., & von Delft, J. (2009) · Physical Review B · doi:10.1103/physrevb.80.165117 · Cited by 196
Spin dynamics and the Haldane gap in the spin-1 quasi-one-dimensional antiferromagnetCsNiCl3
Morra, R. M., Buyers, W. J. L., Armstrong, R. L., & Hirakawa, K. (1988) · Physical Review B · doi:10.1103/physrevb.38.543 · Cited by 189
Guest column: the quantum PCP conjecture
Aharonov, D., Arad, I., & Vidick, T. (2013) · ACM SIGACT News · doi:10.1145/2491533.2491549 · Cited by 185
Dubail, J., & Read, N. (2015) · Physical Review B · doi:10.1103/physrevb.92.205307 · Cited by 176
The Statistical Mechanics of Lattice Gases, Volume I
Simon, B. (1993) · Princeton University Press eBooks · doi:10.1515/9781400863433 · Cited by 174
Realizable Hamiltonians for universal adiabatic quantum computers
Biamonte, J. D., & Love, P. J. (2008) · Physical Review A · doi:10.1103/physreva.78.012352 · Cited by 173
Two soluble models of an antiferromagnetic chain
(1961) · Annals of Physics · doi:10.1016/0003-4916(61)90208-1 · Cited by 171
Complexity of Stoquastic Frustration-Free Hamiltonians
Bravyi, S. B., & Terhal, B. M. (2009) · SIAM Journal on Computing · doi:10.1137/08072689x · Cited by 166
Osborne, T. J. (2012) · Reports on Progress in Physics · doi:10.1088/0034-4885/75/2/022001 · Cited by 165
Approximating Gibbs states of local Hamiltonians efficiently with projected entangled pair states
Molnár, A., Schuch, N., Verstraete, F., & Cirac, J. I. (2015) · Physical Review B · doi:10.1103/physrevb.91.045138 · Cited by 164
Exponential Decay of Correlations Implies Area Law
Brandão, F. G. S. L., & Horodecki, M. (2015) · Communications in Mathematical Physics · doi:10.1007/s00220-014-2213-8 · Cited by 159
Absence of Mott Transition in an Exact Solution of the Short-Range, One-Band Model in One Dimension
Lieb, E. H., & Wu, F. Y. (1968) · Physical Review Letters · doi:10.1103/physrevlett.21.192.2 · Cited by 158
The complexity of quantum spin systems on a two-dimensional square lattice
Oliveira, R. I., & Terhal, B. M. (2008) · CERN Document Server (European Organization for Nuclear Research) · doi:10.5555/2016985.2016987 · Cited by 144
Criticality without Frustration for Quantum Spin-1 Chains
Bravyi, S. B., Caha, L., Movassagh, R., Nagaj, D., & Shor, P. W. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.207202 · Cited by 144
Quantum NP - A SurveyPreprint
Aharonov, D., & Naveh, T. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0210077 · Cited by 143
3-Local Hamiltonian is QMA-complete
Kempe, J., & Regev, O. (2003) · Quantum Information and Computation · doi:10.26421/qic3.3-7 · Cited by 140
Projected Entangled-Pair States Can Describe Chiral Topological States
Wahl, T. B., Tu, H.-H., Schuch, N., & Cirac, J. I. (2013) · Physical Review Letters · doi:10.1103/physrevlett.111.236805 · Cited by 137
The detectability lemma and quantum gap amplification
Aharonov, D., Arad, I., Landau, Z. A., & Vazirani, U. V. (2009) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1536414.1536472 · Cited by 137
Self-citationEntanglement Rates and Area Laws
Acoleyen, K. V., Mariën, M., & Verstraete, F. (2013) · Physical Review Letters · doi:10.1103/physrevlett.111.170501 · Cited by 137
The complexity of stoquastic local Hamiltonian problems
Bravyi, S. B., Divincenzo, D. P., Oliveira, R. I., & Terhal, B. M. (2008) · CERN Document Server (European Organization for Nuclear Research) · doi:10.5555/2011772.2011773 · Cited by 135
Entanglement in a Valence-Bond Solid State
Fan, H., Korepin, V., & Roychowdhury, V. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.227203 · Cited by 134
The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
Krom, M. R. (1967) · Mathematical logic quarterly · doi:10.1002/malq.19670130104 · Cited by 133
Area law for the entropy of low-energy states
Masanes, L. (2009) · Physical Review A · doi:10.1103/physreva.80.052104 · Cited by 116
Improved one-dimensional area law for frustration-free systems
Arad, I., Landau, Z. A., & Vazirani, U. V. (2012) · Physical Review B · doi:10.1103/physrevb.85.195145 · Cited by 108
Self-citationValence Bond Ground States in Isotropic Quantum Antiferromagnets
Affleck, I. K., Kennedy, T., Lieb, É. H., & Tasaki, H. (1988) · Springer eBooks · doi:10.1007/978-3-662-06390-3_19 · Cited by 98
Efficient algorithm for a quantum analogue of 2-SAT
Bravyi, S. (2011) · Contemporary Mathematics · doi:10.1090/conm/536/10552 · Cited by 98 · cited 10×
“If, on the other hand, generateConstraints fails, then we have arrived at a “saturated” system of constraints [Bra06].”
BackgroundMethodInfluentialThe Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
Gottesman, D., & Irani, S. (2009) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2009.22 · Cited by 97
Commutative version of the local Hamiltonian problem and common eigenspace problem
Bravyi, S. B., & Vyalyi, M. (2005) · Quantum Information and Computation · doi:10.26421/qic5.3-2 · Cited by 90
The strong-correlations puzzle
Quintanilla, J., & Hooley, C. (2009) · Physics World · doi:10.1088/2058-7058/22/06/38 · Cited by 81
Aharonov, D., & Eldar, L. (2011) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.58 · Cited by 77
The one dimensional Ising model with a transverse field
(1970) · Annals of Physics · doi:10.1016/0003-4916(70)90030-8 · Cited by 76
The Quantum PCP ConjecturePreprint
Aharonov, D., Arad, I., & Vidick, T. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1309.7495 · Cited by 71
Entanglement Rates and the Stability of the Area Law for the Entanglement Entropy
Mariën, M., Audenaert, K. M. R., Acoleyen, K. V., & Verstraete, F. (2016) · Communications in Mathematical Physics · doi:10.1007/s00220-016-2709-5 · Cited by 70
The Power of Quantum Systems on a Line
Aharonov, D., Gottesman, D., Irani, S., & Kempe, J. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.46 · Cited by 67
Feynman, R. P. (1984) · Conference on Lasers and Electro-Optics · doi:10.1364/cleo.1984.tuaa2 · Cited by 66
New construction for a QMA complete three-local Hamiltonian
Nagaj, D., & Mozes, S. (2007) · Journal of Mathematical Physics · doi:10.1063/1.2748377 · Cited by 62
Bansal, N., Bravyi, S. B., & Terhal, B. M. (2009) · Quantum Information and Computation · doi:10.26421/qic9.7-8-12 · Cited by 61
Approximation Algorithms for QMA-Complete Problems
Gharibian, S., & Kempe, J. (2012) · SIAM Journal on Computing · doi:10.1137/110842272 · Cited by 61
Self-citationComputational Difficulty of Finding Matrix Product Ground States
Schuch, N., Cirac, I., & Verstraete, F. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.250501 · Cited by 60
Interacting Boson Problems Can Be QMA Hard
Wei, T.-C., Mosca, M., & Nayak, A. (2010) · Physical Review Letters · doi:10.1103/physrevlett.104.040501 · Cited by 55
Complexity of commuting Hamiltonians on a square lattice of qubits
Schuch, N. (2011) · Quantum Information and Computation · doi:10.26421/qic11.11-12-1 · Cited by 53
Power law violation of the area law in quantum spin chainsPreprint
Movassagh, R., & Shor, P. W. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1408.1657 · Cited by 52
Ground state entanglement in one-dimensional translationally invariant quantum systems
Irani, S. (2010) · Journal of Mathematical Physics · doi:10.1063/1.3254321 · Cited by 51
Matrix product state and mean-field solutions for one-dimensional systems can be found efficiently
Schuch, N., & Cirac, J. I. (2010) · Physical Review A · doi:10.1103/physreva.82.012314 · Cited by 48
Universal Adiabatic Quantum Computation via the Space-Time Circuit-to-Hamiltonian Construction
Gosset, D., Terhal, B. M., & Vershynina, A. (2015) · Physical Review Letters · doi:10.1103/physrevlett.114.140501 · Cited by 47
Statistics of the Two-Dimensional Ferromagnet
(2020) · Princeton University Press eBooks · doi:10.2307/j.ctv15r58p1.21 · Cited by 47
Product-state Approximations to Quantum Ground StatesPreprint
Brandão, F. G. S. L., & Harrow, A. W. (2013) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 46
Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law
Aharonov, D., Harrow, A. W., Landau, Z. A., Nagaj, D., Szegedy, M., & Vazirani, U. V. (2014) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2014.34 · Cited by 44
Self-citationA Multiprover Interactive Proof System for the Local Hamiltonian Problem
Fitzsimons, J. F., & Vidick, T. (2015) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2688073.2688094 · Cited by 43
Complexity Classification of Local Hamiltonian Problems
Cubitt, T. S., & Montanaro, A. (2014) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2014.21 · Cited by 42
Quantum-Merlin-Arthur–complete problems for stoquastic Hamiltonians and Markov matrices
Jordan, S. P., Gosset, D., & Love, P. J. (2010) · Physical Review A · doi:10.1103/physreva.81.032331 · Cited by 41
The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach
Aharonov, D., Arad, I., Landau, Z. A., & Vazirani, U. V. (2011) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.91 · Cited by 41
Self-citationQuantum 3-SAT Is QMA1-Complete
Gosset, D., & Nagaj, D. (2013) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.86 · Cited by 41
The local Hamiltonian problem on a line with eight staes is QMA-complete
Hallgren, S., Nagaj, D., & Narayanaswami, S. (2013) · Quantum Information and Computation · doi:10.26421/qic13.9-10-1 · Cited by 40
Merlin-Arthur Games and Stoquastic ComplexityPreprint
Bravyi, S. B., Bessen, A. J., & Terhal, B. M. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0611021 · Cited by 40
Area law in one dimension: Degenerate ground states and Renyi entanglement entropyPreprint
Huang, Y. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1403.0327 · Cited by 40
Self-citationTwo-Dimensional Ising Model as a Soluble Problem of Many Fermions
Schultz, T. D., Mattis, D. C., & Lieb, É. H. (2004) · Springer eBooks · doi:10.1007/978-3-662-06390-3_33 · Cited by 39
Entanglement area law from specific heat capacity
Brandão, F. G. S. L., & Cramer, M. (2015) · Physical Review B · doi:10.1103/physrevb.92.115134 · Cited by 37
Local Hamiltonians in Quantum ComputationPreprint
Nagaj, D. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0808.2117 · Cited by 37
Ground State Connectivity of Local Hamiltonians
Gharibian, S., & Sikora, J. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-47672-7_50 · Cited by 35
Self-citationMarriott, C., & Watrous, J. (2004) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2004.1313850 · Cited by 32
The Bose-Hubbard model is QMA-completePreprint
Childs, A. M., Gosset, D., & Webb, Z. (2013) · Cited by 30
Efficient algorithm for approximating one-dimensional ground states
Aharonov, D., Arad, I., & Irani, S. (2010) · Physical Review A · doi:10.1103/physreva.82.012315 · Cited by 28
DENSITY MATRIX RENORMALIZATION GROUP: INTRODUCTION FROM A VARIATIONAL POINT OF VIEW
Nishino, T., Hikihara, T., Okunishi, K., & Hieida, Y. (1999) · International Journal of Modern Physics B · doi:10.1142/s0217979299000023 · Cited by 28
Computing the Degenerate Ground Space of Gapped Spin Chains in Polynomial Time
Chubb, C. T., & Flammia, S. T. (2016) · Chicago Journal of Theoretical Computer Science · doi:10.4086/cjtcs.2016.009 · Cited by 28
PROJECTED ENTANGLED STATES: PROPERTIES AND APPLICATIONS
Verstraete, F., Wolf, M. M., Pérez-García, D., & Cirac, J. I. (2006) · International Journal of Modern Physics B · doi:10.1142/s021797920603620x · Cited by 27
Hardness of Approximation for Quantum Problems
Gharibian, S., & Kempe, J. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31594-7_33 · Cited by 26
Self-citationAharonov, D., & Eldar, L. (2014) · Quantum Information Processing · doi:10.1007/s11128-014-0877-9 · Cited by 26
A polynomial-time algorithm for the ground state of 1D gapped local HamiltoniansPreprint
Landau, Z. A., Vazirani, U. V., & Vidick, T. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1307.5143 · Cited by 25
Self-citationThe Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian ProblemsPreprint
Gottesman, D., & Irani, S. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0905.2419 · Cited by 24
Kay, A. (2007) · Physical Review A · doi:10.1103/physreva.76.030307 · Cited by 21
A Linear Time Algorithm for Quantum 2-SAT
de Beaudrap, N., & Gharibian, S. (2015) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.ccc.2016.27 · Cited by 20
Self-citationTensor network non-zero testing
Gharibian, S., Landau, Z. A., Shin, S. W., & Wang, G. (2015) · Quantum Information and Computation · doi:10.26421/qic15.9-10-7 · Cited by 17
Self-citationAharonov, D., & Eldar, L. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1102.0770 · Cited by 15
Stochastic Error Cancellation in Analog Quantum Simulation
Cai, Y., Tong, Y., & Preskill, J. P. (2023) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.tqc.2024.2 · Cited by 14
Matrix product operators and central elements: classical description of a quantum state
Hastings, M. B. (2012) · Geometry and topology monographs · doi:10.2140/gtm.2012.18.115 · Cited by 13
The Local Hamiltonian problem on a line with eight states is QMA-completePreprint
Hallgren, S., Nagaj, D., & Narayanaswami, S. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1312.1469 · Cited by 13
Monte Carlo simulation of stoquastic HamiltoniansPreprint
Bravyi, S. B. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.2295 · Cited by 13
Research works printed but not linked: 2
- Levin, 1973, Universal sequential search problems, Problems of Information Transmission, 9, 265
- Watrous, 2009, Encyclopedia of Complexity and System Science, chapter Quantum Computational Complexity
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
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
Quantum information processing with superconducting circuits: a review
Wendin, G. (2017) · Reports on Progress in Physics · doi:10.1088/1361-6633/aa7e1a · Cited by 890
Circuit complexity in quantum field theory
Jefferson, R. A., & Myers, R. C. (2017) · Journal of High Energy Physics · doi:10.1007/jhep10(2017)107 · Cited by 412
Quantum Entanglement in Neural Network States
Deng, D.-L., Li, X., & Das Sarma, S. (2017) · Physical Review X · doi:10.1103/physrevx.7.021021 · Cited by 403
Metadata
- Authors
- Gharibian, S., Huang, Y., Landau, Z., & Shin, S. W.
- Affiliations
- University of California, Berkeley (US)
- University of California System (US)
- Venue
- Foundations and Trends® in Theoretical Computer Science
- Publisher
- Emerald
- Published
- 2015-10-13
- Volume
- 10
- Issue
- 3
- Pages
- 159-282
- ISSN
- 1551-305X (ISSN-L)
- 1551-3068
- OpenAlex
- W2116015765
- Cited by
- 144
- References
- 182
- Citations by year
- 2026: 7 · 2025: 31 · 2024: 13 · 2023: 10 · 2022: 8 · 2021: 14 · 2020: 8 · 2019: 16 · 2018: 7 · 2017: 18 · 2016: 6 · 2015: 3
- FWCI
- 11.11
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Foundations and Trends® in Theoretical Computer Science (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (0905626, W911NF-12-1-0541)
- John Templeton Foundation
- Government of Canada
- Indian Institute of Technology Madras
- Defense Advanced Research Projects Agency
- Simons Institute for the Theory of Computing, University of California Berkeley
- Natural Sciences and Engineering Research Council of Canada
- Army Research Office (CCF-0905626, W911NF-09-1-0440, W911NF, W911NF-12-1-0541)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- area law, tensor networks, mean-field theory, identical particles, condensed matter physics
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
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.