Monte Carlo simulation of stoquastic Hamiltonians

Abstract

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 Jerrrum and Sinclair (1993).

19 pages. Version 2: more references on complexity of the ferromagnetic Ising model

References in corpus (4)

• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
• Criticality, the area law, and the computational power of PEPS
• On complexity of the quantum Ising model

Cited by in corpus (8)

• Quantum Hamiltonian Complexity
• Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
• How to simulate quantum measurement without computing marginals
• Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians
• Complexity classification of local Hamiltonian problems
• Tunneling through high energy barriers in simulated quantum annealing
• Ground States of Quantum Many Body Lattice Models via Reinforcement Learning
• Stoquastic ground states are classical thermal distributions