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

A Quantum Algorithm for the Ferromagnetic Ising Model (Manuscript in preparation)

Ashwin Nayak, Universityof Waterloo, Leonard J. Schulman, Umesh V. Vazirani

Published Jan 1, 2008• 0 citations
OpenAlex

Abstract

This manuscript presents a quantum algorithm for the (classical) ferromagnetic Ising model discovered by us in 1997, and refined in subsequent years. A more complete version that includes a discussion of the earlier and related work on the subject, a comparison of the time complexity of the algorithm with the known ecient classical algorithm, and possible improvements and extensions will appear shortly.

Related papers

Non-Hermitian quantum annealing in the ferromagnetic Ising model

Alexander I. Nesterov, Juan Carlos Beas Zepeda, G. P. Berman

We developed a non-Hermitian quantum optimization algorithm to find the ground state of the ferromagnetic Ising model with up to 1024 spins (qubits). Our approach leads to significant reduction of the annealing time. Analytical and numerical results demonstrate that the total annealing time is proportional to $\mathrm{ln}N$, where $N$ is the number of spins. This encouraging result is important in using classical computers in combination with quantum algorithms for the fast solutions of NP-complete problems. Additional research is proposed for extending our dissipative algorithm to more complicated problems.

arXiv:1211.3178•Physical Review A•Apr 25, 2013•10 citations

Quantum Algorithm for the Transverse-Field Ising Model

Robson Giles

•Jan 1, 2024•0 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•40 citations

An algorithm for simulating the Ising model on a type-II quantum computer

Jared H. Cole, Lloyd C. L. Hollenberg, Steven Prawer

arXiv:quant-ph/0404143•Computer Physics Communications•Jun 8, 2004•3 citations

Monte Carlo simulation of stoquastic Hamiltonians

Sergey B. Bravyi

Stoquastic Hamiltonians are characterized by the property that their off-diagonal matrix elements in the standard product basis are real and non-positive. Many interesting quantum models fall into this class including the Transverse field Ising Model (TIM), the Heisenberg model on bipartite graphs, and the bosonic Hubbard model. Here we consider the problem of estimating the ground state energy of a local stoquastic Hamiltonian $H$ with a promise that the ground state of $H$ has a non-negligible correlation with some `guiding' state that admits a concise classical description. A formalized version of this problem called Guided Stoquastic Hamiltonian is shown to be complete for the complexity class $\MA$ (a probabilistic analogue of $\NP$). To prove this result we employ the Projection Monte Carlo algorithm with a variable number of walkers. Secondly, we show that the ground state and thermal equilibrium properties of the ferromagnetic TIM can be simulated in polynomial time on a classical probabilistic computer. This result is based on the approximation algorithm for the classical ferromagnetic Ising model due to Jerrum and Sinclair (1993).

arXiv:1402.2295•Quantum Information and Computation•Oct 1, 2015•86 citations

An algorithm to obtain exact eigenvalues and eigenstates of the arbitrary spin Ising Hamiltonian in d dimensions

J.M. Dixon, Jack A. Tuszyński

Physics Letters A•May 1, 2001•3 citations
This manuscript presents a quantum algorithm for the (classical) ferromagnetic Ising model discovered by us in 1997, and refined in subsequent years. A more complete version that includes a discussion of the earlier and related work on the subject, a comparison of the time complexity of the algorithm with the known ecient classical algorithm, and possible improvements and extensions will appear shortly.
We developed a non-Hermitian quantum optimization algorithm to find the ground state of the ferromagnetic Ising model with up to 1024 spins (qubits). Our approach leads to significant reduction of the annealing time. Analytical and numerical results demonstrate that the total annealing time is proportional to lnN\mathrm{ln}NlnN, where NNN is the number of spins. This encouraging result is important in using classical computers in combination with quantum algorithms for the fast solutions of NP-complete problems. Additional research is proposed for extending our dissipative algorithm to more complicated problems.
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.
Stoquastic Hamiltonians are characterized by the property that their off-diagonal matrix elements in the standard product basis are real and non-positive. Many interesting quantum models fall into this class including the Transverse field Ising Model (TIM), the Heisenberg model on bipartite graphs, and the bosonic Hubbard model. Here we consider the problem of estimating the ground state energy of a local stoquastic Hamiltonian HHH with a promise that the ground state of HHH has a non-negligible correlation with some `guiding' state that admits a concise classical description. A formalized version of this problem called Guided Stoquastic Hamiltonian is shown to be complete for the complexity class $\MA$ (a probabilistic analogue of $\NP$). To prove this result we employ the Projection Monte Carlo algorithm with a variable number of walkers. Secondly, we show that the ground state and thermal equilibrium properties of the ferromagnetic TIM can be simulated in polynomial time on a classical probabilistic computer. This result is based on the approximation algorithm for the classical ferromagnetic Ising model due to Jerrum and Sinclair (1993).