Bravyi, SergeyCarleo, GiuseppeGosset, DavidLiu, Yinchen2024-02-192024-02-192024-02-192023-11-0710.22331/q-2023-11-07-1173https://infoscience.epfl.ch/handle/20.500.14299/204273WOS:001101016700001We consider the computational task of sampling a bit string x from a distribution pi(x) = |(x|0)|2, where 0 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|0)/(x|0) 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.Physical SciencesMonte-CarloComplexitytext::journal::journal article::research article