We consider the computational task of sampling a bit string $x$ from a distribution $\pi(x)=|\langle x|\psi\rangle|^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 $\langle y|\psi\rangle/\langle x|\psi\rangle$ 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.
 Francisco Barahona. On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical and General, 15(10):3241, 1982.
 Philip M Long and Rocco A Servedio. Restricted Boltzmann machines are hard to approximately evaluate or simulate. Proceedings of the 27th International Conference on International Conference on Machine Learning. ICML’10. Haifa, Israel, page 703–710, 2010.
 Sergey Bravyi, David Gosset, and Yinchen Liu. How to simulate quantum measurement without computing marginals. Physical Review Letters, 128(22):220503, 2022.
 Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 20–29, 2003.
 DFB Ten Haaf, HJM Van Bemmel, JMJ Van Leeuwen, W Van Saarloos, and DM Ceperley. Proof for an upper bound in fixed-node Monte Carlo for lattice fermions. Physical Review B, 51(19):13039, 1995.
 Glen Takahara. STAT 455 Stochastic Process Lecture Notes. 2017.
 NV Prokof’Ev, BV Svistunov, and IS Tupitsyn. Exact, complete, and universal continuous-time worldline monte carlo approach to the statistics of discrete quantum systems. Journal of Experimental and Theoretical Physics, 87(2):310–321, 1998.
 Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Harvey B. Meyer, and Peter Shor. Quantum Adiabatic Algorithms, Small Gaps, and Different Paths. Quantum Info. Comput., 11(3):181–214, mar 2011.
 Anne EB Nielsen, J Ignacio Cirac, and Germán Sierra. Laughlin spin-liquid states on lattices obtained from conformal field theory. Physical review letters, 108(25):257206, 2012.
 Aki Vehtari, Andrew Gelman, Daniel Simpson, Bob Carpenter, and Paul-Christian Bürkner. Rank-normalization, folding, and localization: An improved r for assessing convergence of mcmc (with discussion). Bayesian analysis, 16(2):667–718, 2021.
 Sergey Bravyi, Matthias Englbrecht, Robert König, and Nolan Peard. Correcting coherent errors with surface codes. npj Quantum Information, 4(1):1–6, 2018.
 Tom Kennedy. Monte Carlo Methods - a special topics course. 2016.
 Daniel Foreman-Mackey, David W Hogg, Dustin Lang, and Jonathan Goodman. emcee: the mcmc hammer. Publications of the Astronomical Society of the Pacific, 125(925):306, 2013.
The above citations are from SAO/NASA ADS (last updated successfully 2023-12-07 05:43:17). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref's cited-by service no data on citing works was found (last attempt 2023-12-07 05:43:16).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.