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

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

Time Stamp: November 7, 2023 10:36 AM
Source Node: 2371156

Sergey Bravyi1, Giuseppe Carleo2, David Gosset3,4, and Yinchen Liu3,4

1IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, USA
2École Polytechnique Fédérale de Lausanne (EPFL), Institute of Physics, CH-1015 Lausanne, Switzerland
3Department of Combinatorics and Optimization and Institute for Quantum Computing, University of Waterloo
4Perimeter Institute for Theoretical Physics, Waterloo, Canada

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We consider the computational task of sampling a bit string $x$ from a distribution $pi(x)=|langle x|psirangle|^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|psirangle/langle x|psirangle$ 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.

Popular summary

We show how to map a quantum $k$-local Hamiltonian $H$ with the unique ground state $psi$ to a continuous-time Markov Chain with the unique steady distribution describing the measurement of $psi$ in the standard basis. The Markov chain is rapidly mixing whenever the spectral gap of $H$ is at least inverse polynomial in the system size. 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 show that for certain Hamiltonians our Markov Chain gives an efficient classical algorithm for sampling the ground state probability distribution.

â–º BibTeX data

â–º References

[1] Francisco Barahona. On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical and General, 15(10):3241, 1982.
https:/​/​doi.org/​10.1088/​0305-4470/​15/​10/​028

[2] 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.
https:/​/​dl.acm.org/​doi/​abs/​10.5555/​3104322.3104412

[3] W. K. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1):97–109, April 1970.
https:/​/​doi.org/​10.2307/​2334940

[4] David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
https:/​/​doi.org/​10.1090/​mbk/​107

[5] Sergey Bravyi, David Gosset, and Yinchen Liu. How to simulate quantum measurement without computing marginals. Physical Review Letters, 128(22):220503, 2022.
https:/​/​doi.org/​10.1103/​PhysRevLett.128.220503

[6] 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.
https:/​/​doi.org/​10.1145/​780542.780546

[7] Sergey Bravyi and Barbara Terhal. Complexity of stoquastic frustration-free hamiltonians. SIAM Journal on Computing, 39(4):1462–1485, 2010.
https:/​/​doi.org/​10.1137/​08072689X

[8] 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.
https:/​/​doi.org/​10.1103/​physrevb.51.13039

[9] WMC Foulkes, Lubos Mitas, RJ Needs, and Guna Rajagopal. Quantum monte carlo simulations of solids. Reviews of Modern Physics, 73(1):33, 2001.
https:/​/​doi.org/​10.1103/​RevModPhys.73.33

[10] Federico Becca and Sandro Sorella. Quantum Monte Carlo Approaches for Correlated Systems. Cambridge University Press, 2017.
https:/​/​doi.org/​10.1017/​9781316417041

[11] Vojtech Havlicek. Amplitude ratios and neural network quantum states. Quantum, 7:938, 2023.
https:/​/​doi.org/​10.22331/​q-2023-03-02-938

[12] Daniel T Gillespie. Exact stochastic simulation of coupled chemical reactions. The journal of physical chemistry, 81(25):2340–2361, 1977.
https:/​/​doi.org/​10.1021/​j100540a008

[13] Persi Diaconis and Daniel Stroock. Geometric bounds for eigenvalues of Markov chains. The Annals of Applied Probability, pages 36–61, 1991.
https:/​/​doi.org/​10.1214/​aoap/​1177005980

[14] Glen Takahara. STAT 455 Stochastic Process Lecture Notes. 2017.

[15] 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.
https:/​/​doi.org/​10.1134/​1.558661

[16] 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.
https:/​/​doi.org/​10.26421/​qic11.3-4-1

[17] Jean-Marie Stephan and Frank Pollmann. Full counting statistics in the haldane-shastry chain. Physical Review B, 95(3):035119, 2017.
https:/​/​doi.org/​10.1103/​physrevb.95.035119

[18] Shriya Pai, NS Srivatsa, and Anne EB Nielsen. Disordered haldane-shastry model. Physical Review B, 102(3):035117, 2020.
https:/​/​doi.org/​10.1103/​physrevb.102.035117

[19] Joel Klassen and Barbara M Terhal. Two-local qubit hamiltonians: when are they stoquastic? Quantum, 3:139, 2019.
https:/​/​doi.org/​10.22331/​q-2019-05-06-139

[20] 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.
https:/​/​doi.org/​10.1103/​PhysRevLett.108.257206

[21] 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.
https:/​/​doi.org/​10.1214/​20-ba1221

[22] Barbara M Terhal and David P DiVincenzo. Classical simulation of noninteracting-fermion quantum circuits. Physical Review A, 65(3):032325, 2002.
https:/​/​doi.org/​10.1103/​physreva.65.032325

[23] Sergey Bravyi, Matthias Englbrecht, Robert König, and Nolan Peard. Correcting coherent errors with surface codes. npj Quantum Information, 4(1):1–6, 2018.
https:/​/​doi.org/​10.1038/​s41534-018-0106-y

[24] Sergey Bravyi. Contraction of matchgate tensor networks on non-planar graphs. Contemp. Math, 482:179–211, 2009.
https:/​/​doi.org/​10.1090/​conm/​482/​09419

[25] Sergey Bravyi. Lagrangian representation for fermionic linear optics. Quantum Information & Computation, 5(3):216–238, 2005.
https:/​/​doi.org/​10.26421/​qic5.3-3

[26] Tom Kennedy. Monte Carlo Methods – a special topics course. 2016.

[27] 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.
https:/​/​doi.org/​10.1086/​670067

Cited by

[1] Jiaqing Jiang, “Local Hamiltonian Problem with succinct ground state is MA-Complete”, arXiv:2309.10155, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2023-11-07 15:40:06). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2023-11-07 15:40:04: Could not fetch cited-by data for 10.22331/q-2023-11-07-1173 from Crossref. This is normal if the DOI was registered recently.

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.

Time Stamp:

More from Quantum Journal