On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants
arXiv:quant-ph/0309064 · doi:10.1088/1367-2630/6/1/167
Abstract
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 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 polynomial and the partition function for the Potts model.
8 pages, incl. 2 figures. v2: Substantially rewritten
References in corpus (15)
- Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
- From quantum cellular automata to quantum lattice gases
- Efficient Simulation of Quantum Systems by Quantum Computers
- Quantum Algorithms for Fermionic Simulations
- Simulation of topological field theories by quantum computers
- The problem of equilibration and the computation of correlation functions on a quantum computer
- Comparing Quantum Entanglement and Topological Entanglement
- Simulating Ising Spin Glasses on a Quantum Computer
- Calculating the Thermal Rate Constant with Exponential Speed-Up on a Quantum Computer
- Polynomial-Time Simulation of Pairing Models on a Quantum Computer
- Quantum mechanics of lattice gas automata. I. One particle plane waves and potentials
- Exponential Gain in Quantum Computing of Quantum Chaos and Localization
- Quantum Computing of Classical Chaos: Smile of the Arnold-Schrodinger Cat
- Quantum lattice-gas models for the many-body Schrodinger equation
- Strange attractor simulated on a quantum computer
Cited by in corpus (25)
- Quantum Simulation
- Measurement-based quantum computation
- Completeness of the classical 2D Ising model and universal quantum computation
- Classical spin models and the quantum stabilizer formalism
- Quantum Commuting Circuits and Complexity of Ising Partition Functions
- Quantum Discord and Quantum Computing - An Appraisal
- Quantum algorithms for spin models and simulable gate sets for quantum computation
- On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
- Quantum algorithms for classical lattice models
- Completeness of classical spin models and universal quantum computation
- A simple encoding of a quantum circuit amplitude as a matrix permanent
- Measuring complex partition function zeroes of Ising models in quantum simulators
- Classical Ising model test for quantum circuits
- Quantum algorithms for scientific computing
- Arboreal Bound Entanglement
- An algorithmic proof for the completeness of two-dimensional Ising model
- Low Depth Quantum Circuits for Ising Models
- Topological Quantum Statistical Mechanics and Topological Quantum Field Theories
- A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs
- Classical spin systems and the quantum stabilizer formalism: general mappings and applications
- Quantum simulation of classical thermal states
- Partition Function Estimation: Quantum and Quantum-Inspired Algorithms
- Ising models and topological codes: classical algorithms and quantum simulation
- Quantum Annealing Algorithms for Estimating Ising Partition Functions
- Ising-like models on arbitrary graphs : The Hadamard way