A rapidly mixing Markov chain from any gapped quantum many-body system

Abstract

We consider the computational task of sampling a bit string $x$ from a distribution $\pi (x)=|⟨x|\psi ⟩{|}^2$, where $\psi$ is the unique ground state of a local Hamiltonian $H$. Our main result describes a direct link between the inverse spectral gap of $H$ and the mixing time of an associated continuous-time Markov Chain with steady state $\pi$. The Markov Chain can be implemented efficiently whenever ratios of ground state amplitudes $⟨y|\psi ⟩/⟨x|\psi ⟩$ are efficiently computable, the spectral gap of $H$ is at least inverse polynomial in the system size, and the starting state of the chain satisfies a mild technical condition that can be efficiently checked. This extends a previously known relationship between sign-problem free Hamiltonians and Markov chains. The tool which enables this generalization is the so-called fixed-node Hamiltonian construction, previously used in Quantum Monte Carlo simulations to address the fermionic sign problem. We implement the proposed sampling algorithm numerically and use it to sample from the ground state of Haldane-Shastry Hamiltonian with up to 56 qubits. We observe empirically that our Markov chain based on the fixed-node Hamiltonian mixes more rapidly than the standard Metropolis-Hastings Markov chain.

arXiv commentv2:journal version

References in corpus (12)

• emcee: The MCMC Hammer
• Rank-normalization, folding, and localization: An improved $\hat{R}$ for assessing convergence of MCMC
• Exact, Complete, and Universal Continuous-Time Worldline Monte Carlo Approach to the Statistics of Discrete Quantum Systems
• Classical simulation of noninteracting-fermion quantum circuits
• Correcting coherent errors with surface codes
• Proof for an upper bound in fixed-node Monte Carlo for lattice fermions
• Laughlin spin liquid states on lattices obtained from conformal field theory
• Full counting statistics in the Haldane-Shastry chain
• How to simulate quantum measurement without computing marginals
• Two-local qubit Hamiltonians: when are they stoquastic?
• Amplitude Ratios and Neural Network Quantum States
• Disordered Haldane-Shastry model

Cited by in corpus (2)

• Impact of conditional modelling for a universal autoregressive quantum state
• Approximately-symmetric neural networks for quantum spin liquids