On the quantum computational complexity of the Ising spin glass partition function and of knot invariants
Open accessAbstract
It is shown that the canonical problem of classical statistical thermodynamics, the computation of the partition function, is in the case of ± J Ising spin glasses a particular instance of certain simple sums known as quadratically signed weight enumerators (QWGTs). On the other hand, it is known that quantum computing is polynomially equivalent to classical probabilistic computing with an oracle for estimating certain QWGTs. This suggests a connection between the partition function estimation problem for spin glasses and quantum computation. This connection extends to knots and graph theory via the equivalence of the Kauffman bracket polynomial and the partition function for the Potts model.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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?
These connections enable one to phrase statistical physics problems naturally in a quantum mechanical setting.
“For one, these connections enable one to phrase statistical physics problems naturally in a quantum mechanical setting 87,92,95,96,99-102 .”
From Measurement-based quantum computation (2009) · cites this paper as [100]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691 · see citing works
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 4,983 · see citing works
Beitrag zur Theorie des Ferromagnetismus
Ising, E. (1925) · Zeitschrift für Physik · doi:10.1007/bf02980577 · Cited by 3,871 · see citing works
Nonuniversal critical dynamics in Monte Carlo simulations
Swendsen, R. H., & Wang, J. (1987) · Physical Review Letters · doi:10.1103/physrevlett.58.86 · Cited by 2,869 · see citing works
Feynman, R. P. (1986) · Foundations of Physics · doi:10.1007/bf01886518 · Cited by 1,770 · see citing works
A polynomial invariant for knots via von Neumann algebras
Jones, V. F. R. (1985) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-1985-15304-2 · Cited by 1,669 · see citing works
State models and the jones polynomial
Kauffman, L. H. (1987) · Topology · doi:10.1016/0040-9383(87)90009-7 · Cited by 1,465 · see citing works
Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
Abrams, D. S., & Lloyd, S. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.2586 · Cited by 745 · see citing works
From quantum cellular automata to quantum lattice gases
Meyer, D. A. (1996) · Journal of Statistical Physics · doi:10.1007/bf02199356 · Cited by 556 · see citing works
On the computational complexity of the Jones and Tutte polynomials
Jaeger, F., Vertigan, D., & Welsh, D. J. A. (1990) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100068936 · Cited by 500 · see citing works
Simulating quantum systems on a quantum computer
Zalka, C. (1998) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.1998.0162 · Cited by 387 · see citing works
Quantum algorithms for fermionic simulations
Ortiz, G., Gubernatis, J. E., Knill, E., & Laflamme, R. (2001) · Physical Review A · doi:10.1103/physreva.64.022319 · Cited by 347 · see citing works
On knot invariants related to some statistical mechanical models
Jones, V. F. R. (1989) · Pacific Journal of Mathematics · doi:10.2140/pjm.1989.137.311 · Cited by 344 · see citing works
Simulation of Topological Field Theories¶by Quantum Computers
Freedman, M. H., Kitaev, A., & Wang, Z. (2002) · Communications in Mathematical Physics · doi:10.1007/s002200200635 · Cited by 274 · see citing works
Adleman, L. M., DeMarrais, J., & Huang, M.-D. A. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293639 · Cited by 250 · see citing works
Problem of equilibration and the computation of correlation functions on a quantum computer
Terhal, B. M., & Divincenzo, D. P. (2000) · Physical Review A · doi:10.1103/physreva.61.022301 · Cited by 181 · see citing works
Kauffman, L. H. (2001) · Series on knots and everything · doi:10.1142/4256 · Cited by 181 · see citing works
Simulations of Many-Body Quantum Systems by a Quantum ComputerPreprint
Wiesner, S. J. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9603028 · Cited by 158 · see citing works
Quantum entanglement and topological entanglement
Kauffman, L. H., & Lomonaco, S. J. (2002) · New Journal of Physics · doi:10.1088/1367-2630/4/1/373 · Cited by 138 · see citing works
Simulating Ising spin glasses on a quantum computer
Lidar, D. A., & Biham, O. (1997) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.56.3661 · Cited by 119 · see citing works
Self-citationCalculating the thermal rate constant with exponential speedup on a quantum computer
Lidar, D. A., & Wang, H. (1999) · Physical Review E · doi:10.1103/physreve.59.2429 · Cited by 115 · see citing works
Self-citationPolynomial-Time Simulation of Pairing Models on a Quantum Computer
Wu, L.-A., Byrd, M., & Lidar, D. A. (2002) · Physical Review Letters · doi:10.1103/physrevlett.89.057904 · Cited by 106 · see citing works
Self-citationQuantum lattice-gas model for the many-particle Schrödinger equation in d dimensions
Boghosian, B. M., & Taylor, W. (1998) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.57.54 · Cited by 105 · see citing works
Quantum lattice-gas model for computational fluid dynamics
Yepez, J. (2001) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.63.046702 · Cited by 105 · see citing works
Quantum mechanics of lattice gas automata: One-particle plane waves and potentials
Meyer, D. A. (1997) · Physical Review E · doi:10.1103/physreve.55.5261 · Cited by 101 · see citing works
Exponential Gain in Quantum Computing of Quantum Chaos and Localization
Georgeot, B., & Shepelyansky, D. L. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.2890 · Cited by 77 · see citing works
Quantum computing and quadratically signed weight enumerators
Knill, E. H., & Laflamme, R. (2001) · Information Processing Letters · doi:10.1016/s0020-0190(00)00222-2 · Cited by 43 · see citing works
Stable Quantum Computation of Unstable Classical Chaos
Georgeot, B., & Shepelyansky, D. L. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.5393 · Cited by 40 · see citing works
Quantum Lattice-Gas Models for the Many-Body Schrödinger Equation
Boghosian, B. M., & Taylor, W. (1997) · International Journal of Modern Physics C · doi:10.1142/s0129183197000606 · Cited by 39 · see citing works
Quantum computing classical physics
MEYER, D. A. (2002) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.2001.0936 · Cited by 33 · see citing works
California Bans Affirmative Action
Barinaga, M. (1996) · Science · doi:10.1126/science.274.5290.1073 · Cited by 12 · see citing works
Strange attractor simulated on a quantum computer
Terraneo, M., Georgeot, B., & Shepelyansky, D. L. (2003) · The European Physical Journal D · doi:10.1140/epjd/e2002-00218-8 · Cited by 7 · see citing works
Comment on "Stable Quantum Computation of Unstable Classical Chaos"Preprint
Zalka, C. (2001) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0110019 · Cited by 1 · see citing works
Quantum Computing and the Jones PolynomialPreprint
Kauffman, L. H. (2001) · arXiv (Cornell University) · doi:10.48550/arxiv.math/0105255
Efficient Simulation of Quantum Systems by Quantum ComputersPreprint
Zalka, C. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9603026
Statistics of knots and entangled random walksPreprint
Nechaev, S. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.cond-mat/9812205
Flagged first, then by citations
Research works printed but not linked: 9
- Zalka C 1998 Proc. R. Soc. A 454 313
- Meyer D A 2002 Proc. R. Soc. A 360 395
- Jerrum M R and Sinclair A 1990 Proc. 17th ICALP, EATCS p 462
- Randall D and Wilson D B 1999 Sampling Spin Configurations of an Ising System, Proc. 10th Symp. on Discrete Algorithms (SODA) p S959
- Knill E and Laflamme R 2001 Inform. Proc. Lett. 79 173
- Jaeger F, Vertigen D and Welsh D 1990 Math. Proc. Cambridge Phil. Soc. 108 35
- Papadimitriou C H 1995 Computational Complexity (Reading, MA: Addison-Wesley Longman)
- Wilson R J 1997 Introduction to Graph Theory 4th edn (Reading, MA: Addison-Wesley)
- Aharonov D 1998 Quantum computation eprint quant-ph/9812037 · arXiv
Cited by
Sorted by citations
Georgescu, I. M., Ashhab, S., & Nori, F. (2014) · Reviews of Modern Physics · doi:10.1103/revmodphys.86.153 · Cited by 2,932 · see citing works
“In (Lidar, 2004; Lidar and Biham, 1997) an algorithm for the construction of the Gibbs distribution of configurations in the Ising model was developed.”
MethodMeasurement-based quantum computation
Briegel, H. J., Browne, D. E., Dür, W., Raussendorf, R., & Van den Nest, M. (2009) · Nature Physics · doi:10.1038/nphys1157 · Cited by 1,090 · see citing works
Completeness of the Classical 2D Ising Model and Universal Quantum Computation
Van den Nest, M., Dür, W., & Briegel, H. J. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.110501 · Cited by 63 · see citing works
Classical Spin Models and the Quantum-Stabilizer Formalism
den Nest, M. V., Dür, W., & Briegel, H. J. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.117207 · Cited by 56 · see citing works
Quantum algorithms for classical lattice models
De las Cuevas, G., Dür, W., Van den Nest, M., & Martin-Delgado, M. A. (2011) · New Journal of Physics · doi:10.1088/1367-2630/13/9/093021 · Cited by 40 · see citing works
- Authors
- Lidar, D. A.
- Affiliations
- University of Toronto (CA)
- Corresponding author
- Lidar, Daniel A
- Venue
- New Journal of Physics
- Publisher
- IOP Publishing
- Published
- 2004-11-17
- Volume
- 6
- Pages
- 167-167
- ISSN
- 1367-2630 (ISSN-L)
- OpenAlex
- W2107720564
- Cited by
- 33
- References
- 36
- Citations by year
- 2026: 1 · 2024: 1 · 2023: 2 · 2022: 1 · 2021: 1 · 2019: 1 · 2017: 1 · 2015: 2 · 2014: 3 · 2013: 1 · 2012: 1
- FWCI
- 0.68
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Licence
- cc-by
- Locations
- New Journal of Physics (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Alfred P. Sloan Foundation
- 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
- Ising spin glass, partition function, quantum computational complexity, knot invariants, Potts model, statistical mechanics, graph theory
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
