Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians

Abstract

Path integral quantum Monte Carlo (PIMC) is a method for estimating thermal equilibrium properties of stoquastic quantum spin systems by sampling from a classical Gibbs distribution using Markov chain Monte Carlo. The PIMC method has been widely used to study the physics of materials and for simulated quantum annealing, but these successful applications are rarely accompanied by formal proofs that the Markov chains underlying PIMC rapidly converge to the desired equilibrium distribution. In this work we analyze the mixing time of PIMC for 1D stoquastic Hamiltonians, including disordered transverse Ising models (TIM) with long-range algebraically decaying interactions as well as disordered XY spin chains with nearest-neighbor interactions. By bounding the convergence time to the equilibrium distribution we rigorously justify the use of PIMC to approximate partition functions and expectations of observables for these models at inverse temperatures that scale at most logarithmically with the number of qubits. The mixing time analysis is based on the canonical paths method applied to the single-site Metropolis Markov chain for the Gibbs distribution of 2D classical spin models with couplings related to the interactions in the quantum Hamiltonian. Since the system has strongly nonisotropic couplings that grow with system size, it does not fall into the known cases where 2D classical spin models are known to mix rapidly.

arXiv comment26 pages, 2 figures, version published in Quantum

References in corpus (22)

• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Adiabatic Quantum Computing
• Stochastic series expansion method with operator-loop update
• Universal Quantum Hamiltonians
• Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
• Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
• Rigorous RG algorithms and area laws for low energy eigenstates in 1D
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
• Adiabatic optimization versus diffusion Monte Carlo
• Polynomial-time classical simulation of quantum ferromagnets
• Quantum Monte Carlo Simulations of Tunneling in Quantum Adiabatic Optimization
• Off-Diagonal Expansion Quantum Monte Carlo
• Quantum Adiabatic Computation With a Constant Gap is Not Useful in One Dimension
• Quantum annealing of an Ising spin-glass by Green's function Monte Carlo
• Spectral Gap Analysis for Efficient Tunneling in Quantum Adiabatic Optimization
• Diffusion Monte Carlo approach versus adiabatic computation for local Hamiltonians
• Glauber dynamics for the quantum Ising model in a transverse field on a regular tree

Cited by in corpus (8)

• On the complexity of quantum partition functions
• Quantum many-body systems in thermal equilibrium
• Spectral estimation for Hamiltonians: a comparison between classical imaginary-time evolution and quantum real-time evolution
• Lefschetz Thimble Quantum Monte Carlo for Spin Systems
• Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
• Path Integral Monte Carlo in the Angular Momentum Basis for a Chain of Planar Rotors
• Simultaneous Stoquasticity
• Classical Simulation of High Temperature Quantum Ising Models