Rapidly mixing loop representation quantum Monte Carlo for Heisenberg models on star-like bipartite graphs
Jun Takahashi, Sam Slezak, Elizabeth Crosson · 2024
Read Rapidly mixing loop representation quantum Monte Carlo for Heisenberg models on star-like bipartite graphs by Jun Takahashi, Sam Slezak, Elizabeth Crosson (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01452.txt.
Description
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.
Catalog record
| CREATOR | Jun Takahashi, Sam Slezak, Elizabeth Crosson |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-01452
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Rapidly mixing loop representation quantum Monte Carlo for Heisenberg models on star-like bipartite graphs Jun Takahashi, Sam Slezak, Elizabeth Crosson 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 ) 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. 1 Introduction The Heisenberg Hamiltonian couples neighboring spin-1/2 degrees of freedom arranged on fixed spatial sites by the exchange interaction of the form \pm\vec{\sigma}_{i}\cdot\vec{\sigma}_{j}=\pm(X_{i}X_{j}+Y_{i}Y_{j}+Z_{i}Z_{j}) , which models the effective energetic tendencies of neighboring electron spins in molecular orbitals within a solid ( i,j refer to neighboring sites, and \vec{\sigma}=(X,Y,Z) is a vector of Pauli matrices). The coupling -\vec{\sigma}_{i}\cdot\vec{\sigma}_{j} in a Hamiltonian is called ferromagnetic (FM) because it energetically favors alignment of spins, while the coupling +\vec{\sigma}_{i}\cdot\vec{\sigma}_{j} favors anti-alignment and is called antiferromanetic (AFM). Exact solutions for Heisenberg models are known only for a few cases [ 30 , 4 , 51 , 33 ] so approximate or computational solutions are needed to study the model in more complicated geometries such as 2D lattices and beyond. Quantum Monte Carlo (QMC) methods seek computational solutions by reducing the approximation of equilibrium observables in certain quantum spin systems to the problem of sampling classical configurations from a weighted probability distribution. QMC methods use a Markov chain to sample from the target distribution, and Monte Carlo estimation to approximate observables of interest. An important condition for the efficient application of QMC is that the model should not have a sign problem [ 31 , 34 ] , meaning that there should be some choice of local basis in which all of the off-diagonal Hamiltonian matrix elements are real and non-positive. In both Suzuki’s original formulation of QMC [ 53 , 52 ] and more modern QMC treatments for spin systems [ 45 ] , this condition ensures that the paths contributing to the path integral for the ground state all have non-negative weights. More generally, the absence of a sign problem reduces the computational complexity of estimating equilibrium observables [ 13 ] and such models without a sign problem are now commonly called “stoquastic” in the context of Hamiltonian complexity [ 10 , 9 , 7 ] . Ferromagnetic Heisenberg models are always stoquastic (the interaction -(X_{i}X_{j}+Y_{i}Y_{j}+Z_{i}Z_{j}) has all real and non-positive matrix elements in the Z -basis). For the antiferromagnetic interaction (X_{i}X_{j}+Y_{i}Y_{j}+Z_{i}Z_{j}) , the desired property of off-diagonal matrix elements in the Z -basis can be obtained by a local unitary transformation [ 34 ] , (Z\otimes I)\vec{\sigma}_{i}\cdot\vec{\sigma}_{j}(Z\otimes I)=(Z_{i}Z_{j}-X_{i}X_{j}-Y_{i}Y_{j}) , but applying this transformation to successfully render the entire model stoquastic requires that the underlying interactions are bipartite in the graph-theoretic sense (i.e., vertices are two-colorable). Hamiltonian Complexity. Computing the ground state energy of an AFM Heisenberg model on general graphs up to an inverse polynomial precision is known to be QMA -complete, and is essentially regarded as the quantum analog of the classical MaxCut problem [ 17 , 3 ] , thus called QuantumMaxCut in the approximation algorithm community. In contrast, the same problem for bipartite graphs is contained in the more limited complexity class StoqMA [ 13 ] because it is stoquastic as described above. While classical MaxCut is trivial to solve on bipartite graphs, the complexity of QuantumMaxCut for bipartite graphs is unknown and is explicitly raised as an open problem in [ 16 ] . Currenlty, the only proven fact is the containment in StoqMA [ 38 ] , so the possibility is wide open from containment in P to being StoqMA -complete. Classical ground state approximations to the QuantumMaxCut problem on general graphs have been obtained in special cases by semidefinite programming (SDP) heierarchies, generalizing the Goemans-Williamson algorithm for classical MaxCut [ 26 , 57 , 66 , 27 ] . These SDP methods are not explicitly affected by the sign problem, but bipartite graphs (including the star-like graphs we consider) have been an important source of tractable examples for these algorithms. QMC and related methods have been used for proving polynomial-time simulability of a variety of stoquastic systems without NP -hardness obstructions, including 1D spin systems at constant temperature [ 11 ] , ferromagnetic Ising models on general interaction graphs [ 6 ] , high-temperature quantum Ising spin glasses on bounded-degree graphs [ 12 ] , as well as a landmark result by Bravyi and Gosset establishing ground state and thermal state simulation for XY ferromagnets on arbitrary interaction graphs [ 8 ] . We note that this latter result includes XX and YY interactions as long as they are stoquastic (thus somewhat extending the notion of “ferromagnetic”) and also local Z fields, but not ZZ interactions. Another related result is a deterministic quasipolynomial-time simulation of XXZ models with tunable XX,YY, and ZZ interactions as long as the ZZ term dominates the other two in a ferromagnetic way [ 20 ] . Based on the empirical evidence provided by decades of computational studies [ 45 ] , it is fairly plausible that QMC algorithms can approximate ground states of bipartite QuantumMaxCut models on a wide range of interaction graphs in classical polynomial time, but there has been no rigorous proof for efficient convergence of QMC for any bipartite AFM models to date. Our work thus provides a first step along a reasonable approach to putting bipartite cases of QuantumMaxCut in BPP . Markov chains and Mixing Times. To obtain a polynomial-time simulation by QMC, the mixing time of Markov chain that drives the QMC method must scale polynomially with the system size [ 28 ] . The mixing time of a Markov chain characterizes the number of classical updates which suffice to produce each approximate sample from the target distribution - a Markov chain which equilibrates in a time that scales logarithmically in the size of its state space (i.e. polynomially in the number of spins or particles for a quantum system) is called rapidly mixing . A general technique for analyzing the mixing time is to bound it in terms of reciprocal of the spectral gap of the Markov chain transition matrix. To bound the spectral gap of the QMC dynamics for O(1) -bipartite graphs, we use the method of canonical paths due to Jerrum and Sinclair [ 22 , 50 ]