Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0902.4889 · New Journal of Physics

Classical Ising model test for quantum circuits

Joseph Geraci, Daniel A Lidar

Published Jul 28, 2010• 21 citations
arXivHTMLPDF

Abstract

We exploit a recently constructed mapping between quantum circuits and graphs in order to prove that circuits corresponding to certain planar graphs can be efficiently simulated classically. The proof uses an expression for the Ising model partition function in terms of quadratically signed weight enumerators (QWGTs), which are polynomials that arise naturally in an expansion of quantum circuits in terms of rotations involving Pauli matrices. We combine this expression with a known efficient classical algorithm for the Ising partition function of any planar graph in the absence of an external magnetic field, and the Robertson–Seymour theorem from graph theory. We give as an example a set of quantum circuits with a small number of non-nearest-neighbor gates which admit an efficient classical simulation.

DOI
10.1088/1367-2630/12/7/075026

Related papers

On the relation between quantum computation and classical statistical mechanics

Joseph Geraci

We provide a quantum algorithm for the exact evaluation of the Potts partition function for a certain class of restricted instances of graphs that correspond to irreducible cyclic codes. We use the same approach to demonstrate that quantum computers can provide an exponential speed up over the best classical algorithms for the exact evaluation of the weight enumerator polynomial for a family of classical cyclic codes. In addition to this we also provide an efficient quantum approximation algorithm for a function (signed-Euler generating function) closely related to the Ising partition function and demonstrate that this problem is BQP-complete. \n\nWe accomplish the above for the Potts partition function by using a series of links between Gauss sums, classical coding theory, graph theory and the partition function. We exploit the fact that there exists an efficient approximation algorithm for Gauss sums and the fact that this problem is equivalent in complexity to evaluating discrete log. A theorem of McEliece allows one to turn the Gauss sum approximation into an exact evaluation of the Potts partition function. Stripping the physics from this result leaves one with the result for the weight enumerator polynomial. \n\nThe result for the approximation of the signed-Euler generating function was accomplished by fashioning a new mapping between quantum circuits and graphs. The mapping provided us with a way of relating the cycle structure of graphs with quantum circuits. Using a slight variant of this mapping, we present the final result of this thesis which presents a way of testing families of quantum circuits for their classical simulatability. We thus provide an efficient way of deciding whether a quantum circuit provides any additional computational power over classical computation and this is achieved by exploiting the fact that planar instances of the Ising partition function (with no external magnetic field) can be efficiently classically computed.

•Jan 1, 2008•0 citations

Quantum algorithms for classical lattice models

Gemma De las Cuevas, Wolfgang Dür, M Van den Nest +1 more

We give efficient quantum algorithms to estimate the partition function of (i) the six-vertex model on a two-dimensional (2D) square lattice, (ii) the Ising model with magnetic fields on a planar graph, (iii) the Potts model on a quasi-2D square lattice and (iv) the Z 2 lattice gauge theory on a 3D square lattice.Moreover, we prove that these problems are BQP-complete, that is, that estimating these partition functions is as hard as simulating arbitrary quantum computation.The results are proven for a complex parameter regime of the models.The proofs are based on a mapping relating partition functions to quantum circuits introduced by Van den Nest et al (2009 Phys.Rev. A 80 052334) and extended here.

arXiv:1104.2517•New Journal of Physics•Sep 9, 2011•40 citations

Quantum Estimation of the Partition Function for Ising Spin Glasses, Knot Invariants, and Quadratically Signed Weight Enumerators

Daniel A. Lidar

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.

•Sep 8, 2003•0 citations

On the quantum computational complexity of the Ising spin glass partition function and of knot invariants

Daniel A Lidar

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.

arXiv:quant-ph/0309064•New Journal of Physics•Nov 17, 2004•33 citations

Polynomial-Time Classical Simulation of Quantum Ferromagnets

Sergey B. Bravyi, David Gosset

We consider a family of quantum spin systems which includes, as special cases, the ferromagnetic XY model and ferromagnetic Ising model on any graph, with or without a transverse magnetic field. We prove that the partition function of any model in this family can be efficiently approximated to a given relative error ε using a classical randomized algorithm with runtime polynomial in ε^{-1}, system size, and inverse temperature. As a consequence, we obtain a polynomial time algorithm which approximates the free energy or ground energy to a given additive error. We first show how to approximate the partition function by the perfect matching sum of a finite graph with positive edge weights. Although the perfect matching sum is not known to be efficiently approximable in general, the graphs obtained by our method have a special structure which facilitates efficient approximation via a randomized algorithm due to Jerrum and Sinclair.

arXiv:1612.05602•Physical Review Letters•Sep 8, 2017•29 citations

Low depth quantum circuits for Ising models

S. Iblisdir, Mauro Cirio, Octavi Boada +1 more

A scheme for measuring complex temperature partition functions of Ising models is introduced. In the context of ordered qubit registers this scheme finds a natural translation in terms of global operations, and single particle measurements on the edge of the array. Two applications of this scheme are presented. First, through appropriate Wick rotations, those amplitudes can be analytically continued to yield esti-mates for partition functions of Ising models. Bounds on the estimation error, valid with high confidence, are provided and shown to be compatible with previous results. Interestingly, the kind of state prepa-rations and measurements involved in this application can in principle be made “instantaneous", i.e. independent of the system size or the parameters being simulated. Second, the scheme allows to accu-rately estimate some non-trivial invariants of links. A third result concerns the computational power of estimations of partition functions for real temperature classical ferromagnetic Ising models on a square lattice. We provide conditions under which estimating such partition functions allow to reconstruct scat-tering amplitudes of quantum circuits making the problem BQP-hard. Using this mapping, we show that wavefunction overlaps for ground states of quantum Hamiltonians, which can serve as a witness to quantum phase transitions, can be estimated from classical Ising model partition functions. Finally, we show that the ability to accurately measure corner magnetisations on thermal states of two-dimensional Ising models with magnetic field leads to fully polynomial random approximation schemes (FPRAS) for the partition function. Each of these results corresponds to a section of the text that can be essentially read independently. 1

•Jan 1, 2014•12 citations
We exploit a recently constructed mapping between quantum circuits and graphs in order to prove that circuits corresponding to certain planar graphs can be efficiently simulated classically. The proof uses an expression for the Ising model partition function in terms of quadratically signed weight enumerators (QWGTs), which are polynomials that arise naturally in an expansion of quantum circuits in terms of rotations involving Pauli matrices. We combine this expression with a known efficient classical algorithm for the Ising partition function of any planar graph in the absence of an external magnetic field, and the Robertson–Seymour theorem from graph theory. We give as an example a set of quantum circuits with a small number of non-nearest-neighbor gates which admit an efficient classical simulation.
We provide a quantum algorithm for the exact evaluation of the Potts partition function for a certain class of restricted instances of graphs that correspond to irreducible cyclic codes. We use the same approach to demonstrate that quantum computers can provide an exponential speed up over the best classical algorithms for the exact evaluation of the weight enumerator polynomial for a family of classical cyclic codes. In addition to this we also provide an efficient quantum approximation algorithm for a function (signed-Euler generating function) closely related to the Ising partition function and demonstrate that this problem is BQP-complete. \n\nWe accomplish the above for the Potts partition function by using a series of links between Gauss sums, classical coding theory, graph theory and the partition function. We exploit the fact that there exists an efficient approximation algorithm for Gauss sums and the fact that this problem is equivalent in complexity to evaluating discrete log. A theorem of McEliece allows one to turn the Gauss sum approximation into an exact evaluation of the Potts partition function. Stripping the physics from this result leaves one with the result for the weight enumerator polynomial. \n\nThe result for the approximation of the signed-Euler generating function was accomplished by fashioning a new mapping between quantum circuits and graphs. The mapping provided us with a way of relating the cycle structure of graphs with quantum circuits. Using a slight variant of this mapping, we present the final result of this thesis which presents a way of testing families of quantum circuits for their classical simulatability. We thus provide an efficient way of deciding whether a quantum circuit provides any additional computational power over classical computation and this is achieved by exploiting the fact that planar instances of the Ising partition function (with no external magnetic field) can be efficiently classically computed.
We give efficient quantum algorithms to estimate the partition function of (i) the six-vertex model on a two-dimensional (2D) square lattice, (ii) the Ising model with magnetic fields on a planar graph, (iii) the Potts model on a quasi-2D square lattice and (iv) the Z 2 lattice gauge theory on a 3D square lattice.Moreover, we prove that these problems are BQP-complete, that is, that estimating these partition functions is as hard as simulating arbitrary quantum computation.The results are proven for a complex parameter regime of the models.The proofs are based on a mapping relating partition functions to quantum circuits introduced by Van den Nest et al (2009 Phys.Rev. A 80 052334) and extended here.
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.
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.
We consider a family of quantum spin systems which includes, as special cases, the ferromagnetic XY model and ferromagnetic Ising model on any graph, with or without a transverse magnetic field. We prove that the partition function of any model in this family can be efficiently approximated to a given relative error ε using a classical randomized algorithm with runtime polynomial in ε^{-1}, system size, and inverse temperature. As a consequence, we obtain a polynomial time algorithm which approximates the free energy or ground energy to a given additive error. We first show how to approximate the partition function by the perfect matching sum of a finite graph with positive edge weights. Although the perfect matching sum is not known to be efficiently approximable in general, the graphs obtained by our method have a special structure which facilitates efficient approximation via a randomized algorithm due to Jerrum and Sinclair.
A scheme for measuring complex temperature partition functions of Ising models is introduced. In the context of ordered qubit registers this scheme finds a natural translation in terms of global operations, and single particle measurements on the edge of the array. Two applications of this scheme are presented. First, through appropriate Wick rotations, those amplitudes can be analytically continued to yield esti-mates for partition functions of Ising models. Bounds on the estimation error, valid with high confidence, are provided and shown to be compatible with previous results. Interestingly, the kind of state prepa-rations and measurements involved in this application can in principle be made “instantaneous", i.e. independent of the system size or the parameters being simulated. Second, the scheme allows to accu-rately estimate some non-trivial invariants of links. A third result concerns the computational power of estimations of partition functions for real temperature classical ferromagnetic Ising models on a square lattice. We provide conditions under which estimating such partition functions allow to reconstruct scat-tering amplitudes of quantum circuits making the problem BQP-hard. Using this mapping, we show that wavefunction overlaps for ground states of quantum Hamiltonians, which can serve as a witness to quantum phase transitions, can be estimated from classical Ising model partition functions. Finally, we show that the ability to accurately measure corner magnetisations on thermal states of two-dimensional Ising models with magnetic field leads to fully polynomial random approximation schemes (FPRAS) for the partition function. Each of these results corresponds to a section of the text that can be essentially read independently. 1