Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2411.01452

Rapidly mixing loop representation quantum Monte Carlo for Heisenberg models on star-like bipartite graphs

Jun Takahashi, Sam Slezak, Elizabeth Crosson

Published Nov 3, 2024• 9 citations
arXivHTMLPDF

Abstract

Quantum Monte Carlo (QMC) methods have proven invaluable in condensed matter physics, particularly for studying ground states and thermal equilibrium properties of quantum Hamiltonians without a sign problem. Over the past decade, significant progress has also been made on their rigorous convergence analysis. Heisenberg antiferromagnets (AFM) with bipartite interaction graphs are a popular target of computational QMC studies due to their physical importance, but despite the apparent empirical efficiency of these simulations it remains an open question whether efficient classical approximation of the ground energy is possible in general. In this work we introduce a ground state variant of the stochastic series expansion QMC method, and for the special class of AFM on interaction graphs with an $O(1)$-bipartite component (star-like), we prove rapid mixing of the associated QMC Markov chain (polynomial time in the number of qubits) by using Jerrum and Sinclair's method of canonical paths. This is the first Markov chain analysis of a practical class of QMC algorithms with the loop representation of Heisenberg models. Our findings contribute to the broader effort to resolve the computational complexity of Heisenberg AFM on general bipartite interaction graphs.

DOI
10.48550/arxiv.2411.01452

Related papers

Efficient Quantum Monte Carlo through Cluster Expansions

Jorge Sánchez-Segovia, Álvaro M. Alhambra

The sign problem remains a major obstacle to extending the success of Monte Carlo methods to generic quantum many-body systems. A powerful alternative relies on cluster expansions, which provide convergent representations of free energies and related quantities, with applications ranging from tensor network contractions to quantum dynamics and circuits. Within their convergence regime, these expansions often yield deterministic polynomial-time algorithms. However, such methods require exhaustive enumeration of connected clusters, leading to a computational overhead of $(N\varepsilon^{-1})^{\mathcal{O}(\logΔ)}$, where $N$ is the system size, $\varepsilon$ the desired precision, and $Δ$ the interaction-graph degree. This becomes particularly severe in long-range systems, where $Δ\equiv N$, resulting in quasi-polynomial runtimes. Here, we introduce a Markov chain algorithm that samples cluster expansions directly in the space of connected clusters, replacing deterministic enumeration by Monte Carlo sampling. Because sampling occurs in an abstract cluster space rather than a physical configuration space, the conventional exponential sign problem is absent within the convergence regime. For general polymer models, we establish an FPRAS with runtime $\tilde{\mathcal{O}}(N^4\varepsilon^{-3})$. For quantum partition functions at temperatures $β\leqβ_{\mathrm{sampling}}\equiv\mathcal{O}(1)$, this improves to $\tilde{\mathcal{O}}(N^{3+1/D}\varepsilon^{-3})$, where $D$ is the lattice dimension. The framework directly applies to long-range quantum systems with interactions $\propto1/r^α$, including $2$-local models with $α>2D$.

quant-pharXiv:2610.03893•Oct 6, 2026•0 citations

Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians

Elizabeth Crosson, Aram W. Harrow

Path integral quantum Monte Carlo (PIMC) is a method for estimating thermal equilibrium properties of stoquastic quantum spin systems by sampling from a classical Gibbs distribution using Markov chain Monte Carlo. The PIMC method has been widely used to study the physics of materials and for simulated quantum annealing, but these successful applications are rarely accompanied by formal proofs that the Markov chains underlying PIMC rapidly converge to the desired equilibrium distribution. In this work we analyze the mixing time of PIMC for 1D stoquastic Hamiltonians, including disordered transverse Ising models (TIM) with long-range algebraically decaying interactions as well as disordered XY spin chains with nearest-neighbor interactions. By bounding the convergence time to the equilibrium distribution we rigorously justify the use of PIMC to approximate partition functions and expectations of observables for these models at inverse temperatures that scale at most logarithmically with the number of qubits. The mixing time analysis is based on the canonical paths method applied to the single-site Metropolis Markov chain for the Gibbs distribution of 2D classical spin models with couplings related to the interactions in the quantum Hamiltonian. Since the system has strongly nonisotropic couplings that grow with system size, it does not fall into the known cases where 2D classical spin models are known to mix rapidly.

arXiv:1812.02144•Quantum•Feb 11, 2021•21 citations

Stochastic series expansion method with operator-loop update

Anders W. Sandvik

A cluster update (the ``operator loop'') is developed within the framework of a numerically exact quantum Monte Carlo method based on the power series expansion of $\mathrm{exp}(\ensuremath{-}\ensuremath{\beta}H)$ (stochastic series expansion). The method is generally applicable to a wide class of lattice Hamiltonians for which the expansion is positive definite. For some important models the operator-loop algorithm is more efficient than loop updates previously developed for ``worldline'' simulations. The method is here tested on a two-dimensional anisotropic Heisenberg antiferromagnet in a magnetic field.

arXiv:cond-mat/9902226•Physical review. B, Condensed matter•Jun 1, 1999•761 citations

Monte Carlo simulation of stoquastic Hamiltonians

Sergey B. Bravyi

Stoquastic Hamiltonians are characterized by the property that their off-diagonal matrix elements in the standard product basis are real and non-positive. Many interesting quantum models fall into this class including the Transverse field Ising Model (TIM), the Heisenberg model on bipartite graphs, and the bosonic Hubbard model. Here we consider the problem of estimating the ground state energy of a local stoquastic Hamiltonian $H$ with a promise that the ground state of $H$ has a non-negligible correlation with some `guiding' state that admits a concise classical description. A formalized version of this problem called Guided Stoquastic Hamiltonian is shown to be complete for the complexity class $\MA$ (a probabilistic analogue of $\NP$). To prove this result we employ the Projection Monte Carlo algorithm with a variable number of walkers. Secondly, we show that the ground state and thermal equilibrium properties of the ferromagnetic TIM can be simulated in polynomial time on a classical probabilistic computer. This result is based on the approximation algorithm for the classical ferromagnetic Ising model due to Jerrum and Sinclair (1993).

arXiv:1402.2295•Quantum Information and Computation•Oct 1, 2015•86 citations

Fixed-point quantum Monte Carlo method: A combination of density-matrix quantum Monte Carlo method and stochastic unravellings

Romain Chessex, Massimo Borrelli, Hans Christian Öttinger

We present an alternative approach to the study of equilibrium properties in many-body quantum physics. Our method takes inspiration from density-matrix quantum Monte Carlo in dealing with the sign problem and incorporates additional features. First of all, the dynamics is transferred to the Laplace representation where an exact equation can be derived and solved using an evolution step that, unlike most Monte Carlo methods, is not a priori physically bounded. Moreover, the spawning events are formulated in terms of two-process stochastic unravellings of quantum master equations, a formalism that is particularly useful when working with density matrices. Last, our approach is perturbative in nature, with the free part being integrated exactly and, as such, the convergence is greatly accelerated when the interaction parameter is small. We benchmark our method by applying it to two case studies in condensed-matter physics, perform some ground-state calculations, show its accuracy, and further discuss its efficiency.

arXiv:2201.01383•Physical Review A•Jun 3, 2022•4 citations

Electronic structure quantum Monte Carlo

Michal Bajdich, Luboš Mitáš

Electronic structure quantum Monte Carlo Quantum Monte Carlo (QMC) is an advanced simulation methodology for studies of manybody quantum systems. The QMC approaches combine analytical insights with stochastic computational techniques for efficient solution of several classes of important many-body problems such as the stationary Schrödinger equation. QMC methods of various flavors have been applied to a great variety of systems spanning continuous and lattice quantum models, molecular and condensed systems, BEC-BCS ultracold condensates, nuclei, etc. In this review, we focus on the electronic structure QMC, i.e., methods relevant for systems described by the electron-ion Hamiltonians. Some of the key QMC achievements include direct treatment of electron correlation, accuracy in predicting energy differences and favorable scaling in the system size. Calculations of atoms, molecules, clusters and solids have demonstrated QMC applicability to real systems with hundreds of electrons while providing 90-95% of the correlation energy and energy differences typically within a few percent of experiments. Advances in accuracy beyond these limits are hampered by the so-called fixed-node approximation which is used to circumvent the notorious fermion sign problem. Many-body nodes of fermion states and their properties have therefore become one of the important topics for further progress in predictive power and efficiency of QMC calculations. Some of our recent results on the wave function nodes and related nodal domain topologies will be briefly reviewed. This includes analysis of few-electron systems and descriptions of exact and approximate nodes using transformations and projections of the highly-dimensional nodal hypersurfaces into the 3D space. Studies of fermion nodes offer new insights into topological properties of eigenstates such as explicit demonstrations that generic fermionic ground states exhibit the minimal number of two nodal domains. Recently proposed trial wave functions based on Pfaffians with pairing orbitals are presented and their nodal properties are tested in calculations of first row atoms and molecules. Finally, backflow "dressed" coordinates are introduced as another possibility for capturing correlation effects and for decreasing the fixed-node bias.

arXiv:1008.2369•Acta Physica Slovaca Reviews and Tutorials•Apr 1, 2009•36 citations
Quantum Monte Carlo (QMC) methods have proven invaluable in condensed matter physics, particularly for studying ground states and thermal equilibrium properties of quantum Hamiltonians without a sign problem. Over the past decade, significant progress has also been made on their rigorous convergence analysis. Heisenberg antiferromagnets (AFM) with bipartite interaction graphs are a popular target of computational QMC studies due to their physical importance, but despite the apparent empirical efficiency of these simulations it remains an open question whether efficient classical approximation of the ground energy is possible in general. In this work we introduce a ground state variant of the stochastic series expansion QMC method, and for the special class of AFM on interaction graphs with an O(1)O(1)O(1)-bipartite component (star-like), we prove rapid mixing of the associated QMC Markov chain (polynomial time in the number of qubits) by using Jerrum and Sinclair's method of canonical paths. This is the first Markov chain analysis of a practical class of QMC algorithms with the loop representation of Heisenberg models. Our findings contribute to the broader effort to resolve the computational complexity of Heisenberg AFM on general bipartite interaction graphs.
The sign problem remains a major obstacle to extending the success of Monte Carlo methods to generic quantum many-body systems. A powerful alternative relies on cluster expansions, which provide convergent representations of free energies and related quantities, with applications ranging from tensor network contractions to quantum dynamics and circuits. Within their convergence regime, these expansions often yield deterministic polynomial-time algorithms. However, such methods require exhaustive enumeration of connected clusters, leading to a computational overhead of (Nε−1)O(log⁡Δ)(N\varepsilon^{-1})^{\mathcal{O}(\logΔ)}(Nε−1)O(logΔ), where NNN is the system size, ε\varepsilonε the desired precision, and ΔΔΔ the interaction-graph degree. This becomes particularly severe in long-range systems, where Δ≡NΔ\equiv NΔ≡N, resulting in quasi-polynomial runtimes. Here, we introduce a Markov chain algorithm that samples cluster expansions directly in the space of connected clusters, replacing deterministic enumeration by Monte Carlo sampling. Because sampling occurs in an abstract cluster space rather than a physical configuration space, the conventional exponential sign problem is absent within the convergence regime. For general polymer models, we establish an FPRAS with runtime O~(N4ε−3)\tilde{\mathcal{O}}(N^4\varepsilon^{-3})O~(N4ε−3). For quantum partition functions at temperatures β≤βsampling≡O(1)β\leqβ_{\mathrm{sampling}}\equiv\mathcal{O}(1)β≤βsampling​≡O(1), this improves to O~(N3+1/Dε−3)\tilde{\mathcal{O}}(N^{3+1/D}\varepsilon^{-3})O~(N3+1/Dε−3), where DDD is the lattice dimension. The framework directly applies to long-range quantum systems with interactions ∝1/rα\propto1/r^α∝1/rα, including 222-local models with α>2Dα>2Dα>2D.
Path integral quantum Monte Carlo (PIMC) is a method for estimating thermal equilibrium properties of stoquastic quantum spin systems by sampling from a classical Gibbs distribution using Markov chain Monte Carlo. The PIMC method has been widely used to study the physics of materials and for simulated quantum annealing, but these successful applications are rarely accompanied by formal proofs that the Markov chains underlying PIMC rapidly converge to the desired equilibrium distribution. In this work we analyze the mixing time of PIMC for 1D stoquastic Hamiltonians, including disordered transverse Ising models (TIM) with long-range algebraically decaying interactions as well as disordered XY spin chains with nearest-neighbor interactions. By bounding the convergence time to the equilibrium distribution we rigorously justify the use of PIMC to approximate partition functions and expectations of observables for these models at inverse temperatures that scale at most logarithmically with the number of qubits. The mixing time analysis is based on the canonical paths method applied to the single-site Metropolis Markov chain for the Gibbs distribution of 2D classical spin models with couplings related to the interactions in the quantum Hamiltonian. Since the system has strongly nonisotropic couplings that grow with system size, it does not fall into the known cases where 2D classical spin models are known to mix rapidly.
A cluster update (the ``operator loop'') is developed within the framework of a numerically exact quantum Monte Carlo method based on the power series expansion of $\mathrm{exp}(\ensuremath{-}\ensuremath{\beta}H)$ (stochastic series expansion). The method is generally applicable to a wide class of lattice Hamiltonians for which the expansion is positive definite. For some important models the operator-loop algorithm is more efficient than loop updates previously developed for ``worldline'' simulations. The method is here tested on a two-dimensional anisotropic Heisenberg antiferromagnet in a magnetic field.
Stoquastic Hamiltonians are characterized by the property that their off-diagonal matrix elements in the standard product basis are real and non-positive. Many interesting quantum models fall into this class including the Transverse field Ising Model (TIM), the Heisenberg model on bipartite graphs, and the bosonic Hubbard model. Here we consider the problem of estimating the ground state energy of a local stoquastic Hamiltonian HHH with a promise that the ground state of HHH has a non-negligible correlation with some `guiding' state that admits a concise classical description. A formalized version of this problem called Guided Stoquastic Hamiltonian is shown to be complete for the complexity class $\MA$ (a probabilistic analogue of $\NP$). To prove this result we employ the Projection Monte Carlo algorithm with a variable number of walkers. Secondly, we show that the ground state and thermal equilibrium properties of the ferromagnetic TIM can be simulated in polynomial time on a classical probabilistic computer. This result is based on the approximation algorithm for the classical ferromagnetic Ising model due to Jerrum and Sinclair (1993).
We present an alternative approach to the study of equilibrium properties in many-body quantum physics. Our method takes inspiration from density-matrix quantum Monte Carlo in dealing with the sign problem and incorporates additional features. First of all, the dynamics is transferred to the Laplace representation where an exact equation can be derived and solved using an evolution step that, unlike most Monte Carlo methods, is not a priori physically bounded. Moreover, the spawning events are formulated in terms of two-process stochastic unravellings of quantum master equations, a formalism that is particularly useful when working with density matrices. Last, our approach is perturbative in nature, with the free part being integrated exactly and, as such, the convergence is greatly accelerated when the interaction parameter is small. We benchmark our method by applying it to two case studies in condensed-matter physics, perform some ground-state calculations, show its accuracy, and further discuss its efficiency.
Electronic structure quantum Monte Carlo Quantum Monte Carlo (QMC) is an advanced simulation methodology for studies of manybody quantum systems. The QMC approaches combine analytical insights with stochastic computational techniques for efficient solution of several classes of important many-body problems such as the stationary Schrödinger equation. QMC methods of various flavors have been applied to a great variety of systems spanning continuous and lattice quantum models, molecular and condensed systems, BEC-BCS ultracold condensates, nuclei, etc. In this review, we focus on the electronic structure QMC, i.e., methods relevant for systems described by the electron-ion Hamiltonians. Some of the key QMC achievements include direct treatment of electron correlation, accuracy in predicting energy differences and favorable scaling in the system size. Calculations of atoms, molecules, clusters and solids have demonstrated QMC applicability to real systems with hundreds of electrons while providing 90-95% of the correlation energy and energy differences typically within a few percent of experiments. Advances in accuracy beyond these limits are hampered by the so-called fixed-node approximation which is used to circumvent the notorious fermion sign problem. Many-body nodes of fermion states and their properties have therefore become one of the important topics for further progress in predictive power and efficiency of QMC calculations. Some of our recent results on the wave function nodes and related nodal domain topologies will be briefly reviewed. This includes analysis of few-electron systems and descriptions of exact and approximate nodes using transformations and projections of the highly-dimensional nodal hypersurfaces into the 3D space. Studies of fermion nodes offer new insights into topological properties of eigenstates such as explicit demonstrations that generic fermionic ground states exhibit the minimal number of two nodal domains. Recently proposed trial wave functions based on Pfaffians with pairing orbitals are presented and their nodal properties are tested in calculations of first row atoms and molecules. Finally, backflow "dressed" coordinates are introduced as another possibility for capturing correlation effects and for decreasing the fixed-node bias.