Polynomial-time classical simulation of quantum ferromagnets

Abstract

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 E using a classical randomized algorithm with runtime polynomial in 1/E, 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.

References in corpus (1)

• The Magnus expansion and some of its applications

Cited by in corpus (22)

• A Theory of Trotter Error
• Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states
• Hamiltonian simulation with random inputs
• Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
• Projective quantum Monte Carlo simulations guided by unrestricted neural network states
• Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
• On the complexity of quantum partition functions
• Quantum many-body systems in thermal equilibrium
• How to simulate quantum measurement without computing marginals
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Two-local qubit Hamiltonians: when are they stoquastic?
• Entanglement accelerates quantum simulation
• Understanding Quantum Tunneling using Diffusion Monte Carlo Simulations
• Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians
• Spectral estimation for Hamiltonians: a comparison between classical imaginary-time evolution and quantum real-time evolution
• Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians
• Exploiting anticommutation in Hamiltonian simulation
• Oracle complexity classes and local measurements on physical Hamiltonians
• Classical restrictions of generic matrix product states are quasi-locally Gibbsian
• Sampling and the complexity of nature
• Classical Simulation of High Temperature Quantum Ising Models
• Error Interference in Quantum Simulation