On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants

DOI10.1088/1367-2630/6/1/167arXivquant-ph/0309064MaRDI QIDQ6501875

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.

This page was built for publication: On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6501875)