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

Sergey Bravyi; Giuseppe Carleo; David Gosset; Yinchen Liu

doi:10.22331/q-2023-11-07-1173

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

Sergey Bravyi¹, Giuseppe Carleo², David Gosset^3,4, and Yinchen Liu^3,4

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

Published:	2023-11-07, volume 7, page 1173
Eprint:	arXiv:2207.07044v2
Doi:	https://doi.org/10.22331/q-2023-11-07-1173
Citation:	Quantum 7, 1173 (2023).

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|\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.

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

@article{Bravyi2023rapidlymixingmarkov,
  doi = {10.22331/q-2023-11-07-1173},
  url = {https://doi.org/10.22331/q-2023-11-07-1173},
  title = {A rapidly mixing {M}arkov chain from any gapped quantum many-body system},
  author = {Bravyi, Sergey and Carleo, Giuseppe and Gosset, David and Liu, Yinchen},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {1173},
  month = nov,
  year = {2023}
}

► 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] Massimo Bortone, Yannic Rath, and George H. Booth, "Impact of conditional modelling for a universal autoregressive quantum state", Quantum 8, 1245 (2024).

[2] Jiaqing Jiang, "Local Hamiltonian Problem with Succinct Ground State is MA-Complete", PRX Quantum 6 2, 020312 (2025).

[3] Dominik S. Kufel, Jack Kemp, DinhDuy Vu, Simon M. Linsel, Chris R. Laumann, and Norman Y. Yao, "Approximately Symmetric Neural Networks for Quantum Spin Liquids", Physical Review Letters 135 5, 056702 (2025).

[4] Abdessatar Souissi, "Ergodic theory of inhomogeneous quantum processes", Quantum Information Processing 25 7, 220 (2026).

[5] Ángela Capel, Paul Gondolf, Jan Kochanowski, and Cambyse Rouzé, "Quasi-optimal Sampling from Gibbs States via Non-commutative Optimal Transport Metrics", Annales Henri Poincaré (2025).

[6] Antoine Misery, Luca Gravina, Alessandro Santini, and Filippo Vicentini, "Looking elsewhere: improving variational Monte Carlo gradients by importance sampling", Machine Learning: Science and Technology 7 1, 015035 (2026).

[7] Yixuan Ma, Chang Liu, Weikang Li, Shun-Yao Zhang, Lu-Ming Duan, Yukai Wu, and Dong-Ling Deng, "Solving excited states for long-range interacting trapped ions with neural networks", Science Bulletin (2026).

[8] Gabriel Waite and Michael J. Bremner, "The Complexity of Local Stoquastic Hamiltonians on 2D Lattices", Quantum 10, 2097 (2026).

[9] Gabriel Waite, "The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians", arXiv:2509.25829, (2025).

[10] Gabriel Waite and Karl Lin, "On the Complexity of the Succinct State Local Hamiltonian Problem", arXiv:2509.25821, (2025).

[11] Mingyu Sun, Gabriel Waite, Michael Bremner, and Christopher Ferrie, "Efficient Fidelity Estimation with Few Local Pauli Measurements", arXiv:2510.08155, (2025).

[12] Gabriel Waite and Michael J. Bremner, "The Complexity of Local Stoquastic Hamiltonians on 2D Lattices", arXiv:2502.14244, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 08:35:08) and SAO/NASA ADS (last updated successfully 2026-08-09 20:19:45). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-08-10 08:35:08: Cannot retrieve data from ADS due to rate limitations.

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.