Classical algorithms for Forrelation
Sergey Bravyi, David Gosset, et al.
QIP 2022
We consider the computational task of sampling a bit string x from a distribution π(x) = |〈x|ψ〉|2, where ψ 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 π. The Markov Chain can be implemented efficiently whenever ratios of ground state amplitudes 〈y|ψ〉/〈x|ψ〉 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.
Sergey Bravyi, David Gosset, et al.
QIP 2022
Giacomo Torlai, Christopher J. Wood, et al.
Nature Communications
Sergey Bravyi, David Poulin, et al.
Physical Review Letters
Tanvi Gujarati, Andrew Eddins, et al.
APS March Meeting 2021