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:0805.1214 · Physical Review A

Quantum algorithms for spin models and simulable gate sets for quantum computation

M. Van den Nest, Wolfgang Dür, Robert Raussendorf, Hans J. Briegel

Published Nov 30, 2009• 35 citations
arXivHTMLPDF

Abstract

We present simple mappings between classical lattice models and quantum circuits, which provide a systematic formalism to obtain quantum algorithms to approximate partition functions of lattice models in certain complex-parameter regimes. We, e.g., present an efficient quantum algorithm for the six-vertex model as well as a two-dimensional Ising-type model. We show that classically simulating these (complex-parameter) spin models is as hard as simulating universal quantum computation, i.e., BQP complete (BQP denotes bounded-error quantum polynomial time). Furthermore, our mappings provide a framework to obtain efficiently simulable quantum gate sets from exactly solvable classical models. We, e.g., show that the simulability of Valiant's match gates can be recovered by using the solvability of the free-fermion eight-vertex model.

DOI
10.1103/physreva.80.052334

Related papers

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 algorithm for an additive approximation of Ising partition functions

Akira Matsuo, Keisuke Fujii, Nobuyuki Imoto

We investigate quantum-computational complexity of calculating partition functions of Ising models. We construct a quantum algorithm for an additive approximation of Ising partition functions on square lattices. To this end, we utilize the overlap mapping developed by M. Van den Nest, W. D\"ur, and H. J. Briegel [Phys. Rev. Lett. 98, 117207 (2007)] and its interpretation through measurement-based quantum computation (MBQC). We specify an algorithmic domain, on which the proposed algorithm works, and an approximation scale, which determines the accuracy of the approximation. We show that the proposed algorithm performs a nontrivial task, which would be intractable on any classical computer, by showing that the problem that is solvable by the proposed quantum algorithm is BQP-complete. In the construction of the BQP-complete problem coupling strengths and magnetic fields take complex values. However, the Ising models that are of central interest in statistical physics and computer science consist of real coupling strengths and magnetic fields. Thus we extend the algorithmic domain of the proposed algorithm to such a real physical parameter region and calculate the approximation scale explicitly. We found that the overlap mapping and its MBQC interpretation improve the approximation scale exponentially compared to a straightforward constant-depth quantum algorithm. On the other hand, the proposed quantum algorithm also provides partial evidence that there exist no efficient classical algorithm for a multiplicative approximation of the Ising partition functions even on the square lattice. This result supports the observation that the proposed quantum algorithm also performs a nontrivial task in the physical parameter region.

arXiv:1405.2749•Physical Review A•Aug 5, 2014•17 citations

Completeness of classical spin models and universal quantum computation

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

We study mappings between distinct classical spin systems that leave the partition function invariant. As recently shown in [Phys. Rev. Lett. 100, 110501 (2008)], the partition function of the 2D square lattice Ising model in the presence of an inhomogeneous magnetic field, can specialize to the partition function of any Ising system on an arbitrary graph. In this sense the 2D Ising model is said to be "complete". However, in order to obtain the above result, the coupling strengths on the 2D lattice must assume complex values, and thus do not allow for a physical interpretation. Here we show how a complete model with real -and, hence, "physical"- couplings can be obtained if the 3D Ising model is considered. We furthermore show how to map general q-state systems with possibly many-body interactions to the 2D Ising model with complex parameters, and give completeness results for these models with real parameters. We also demonstrate that the computational overhead in these constructions is in all relevant cases polynomial. These results are proved by invoking a recently found cross-connection between statistical mechanics and quantum information theory, where partition functions are expressed as quantum mechanical amplitudes. Within this framework, there exists a natural correspondence between many-body quantum states that allow universal quantum computation via local measurements only, and complete classical spin systems.

arXiv:0812.2368•Journal of Statistical Mechanics Theory and Experiment•Jul 1, 2009•20 citations

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

Classical Ising model test for quantum circuits

Joseph Geraci, Daniel A Lidar

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.

arXiv:0902.4889•New Journal of Physics•Jul 28, 2010•21 citations

Completeness of the Classical 2D Ising Model and Universal Quantum Computation

M. Van den Nest, Wolfgang Dür, Hans J. Briegel

We prove that the 2D Ising model is complete in the sense that the partition function of any classical q-state spin model (on an arbitrary graph) can be expressed as a special instance of the partition function of a 2D Ising model with complex inhomogeneous couplings and external fields. In the case where the original model is an Ising or Potts-type model, we find that the corresponding 2D square lattice requires only polynomially more spins with respect to the original one, and we give a constructive method to map such models to the 2D Ising model. For more general models the overhead in system size may be exponential. The results are established by connecting classical spin models with measurement-based quantum computation and invoking the universality of the 2D cluster states.

arXiv:0708.2275•Physical Review Letters•Mar 17, 2008•63 citations
We present simple mappings between classical lattice models and quantum circuits, which provide a systematic formalism to obtain quantum algorithms to approximate partition functions of lattice models in certain complex-parameter regimes. We, e.g., present an efficient quantum algorithm for the six-vertex model as well as a two-dimensional Ising-type model. We show that classically simulating these (complex-parameter) spin models is as hard as simulating universal quantum computation, i.e., BQP complete (BQP denotes bounded-error quantum polynomial time). Furthermore, our mappings provide a framework to obtain efficiently simulable quantum gate sets from exactly solvable classical models. We, e.g., show that the simulability of Valiant's match gates can be recovered by using the solvability of the free-fermion eight-vertex model.
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.
We investigate quantum-computational complexity of calculating partition functions of Ising models. We construct a quantum algorithm for an additive approximation of Ising partition functions on square lattices. To this end, we utilize the overlap mapping developed by M. Van den Nest, W. D\"ur, and H. J. Briegel [Phys. Rev. Lett. 98, 117207 (2007)] and its interpretation through measurement-based quantum computation (MBQC). We specify an algorithmic domain, on which the proposed algorithm works, and an approximation scale, which determines the accuracy of the approximation. We show that the proposed algorithm performs a nontrivial task, which would be intractable on any classical computer, by showing that the problem that is solvable by the proposed quantum algorithm is BQP-complete. In the construction of the BQP-complete problem coupling strengths and magnetic fields take complex values. However, the Ising models that are of central interest in statistical physics and computer science consist of real coupling strengths and magnetic fields. Thus we extend the algorithmic domain of the proposed algorithm to such a real physical parameter region and calculate the approximation scale explicitly. We found that the overlap mapping and its MBQC interpretation improve the approximation scale exponentially compared to a straightforward constant-depth quantum algorithm. On the other hand, the proposed quantum algorithm also provides partial evidence that there exist no efficient classical algorithm for a multiplicative approximation of the Ising partition functions even on the square lattice. This result supports the observation that the proposed quantum algorithm also performs a nontrivial task in the physical parameter region.
We study mappings between distinct classical spin systems that leave the partition function invariant. As recently shown in [Phys. Rev. Lett. 100, 110501 (2008)], the partition function of the 2D square lattice Ising model in the presence of an inhomogeneous magnetic field, can specialize to the partition function of any Ising system on an arbitrary graph. In this sense the 2D Ising model is said to be "complete". However, in order to obtain the above result, the coupling strengths on the 2D lattice must assume complex values, and thus do not allow for a physical interpretation. Here we show how a complete model with real -and, hence, "physical"- couplings can be obtained if the 3D Ising model is considered. We furthermore show how to map general q-state systems with possibly many-body interactions to the 2D Ising model with complex parameters, and give completeness results for these models with real parameters. We also demonstrate that the computational overhead in these constructions is in all relevant cases polynomial. These results are proved by invoking a recently found cross-connection between statistical mechanics and quantum information theory, where partition functions are expressed as quantum mechanical amplitudes. Within this framework, there exists a natural correspondence between many-body quantum states that allow universal quantum computation via local measurements only, and complete classical spin systems.
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 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 prove that the 2D Ising model is complete in the sense that the partition function of any classical q-state spin model (on an arbitrary graph) can be expressed as a special instance of the partition function of a 2D Ising model with complex inhomogeneous couplings and external fields. In the case where the original model is an Ising or Potts-type model, we find that the corresponding 2D square lattice requires only polynomially more spins with respect to the original one, and we give a constructive method to map such models to the 2D Ising model. For more general models the overhead in system size may be exponential. The results are established by connecting classical spin models with measurement-based quantum computation and invoking the universality of the 2D cluster states.