Classical Estimation of the Free Energy and Quantum Gibbs Sampling from the Markov Entropy Decomposition
Samuel O. Scalet, Angela Capel, Anirban N. Chowdhury, Hamza Fawzi, Omar Fawzi, Isaac H. Kim, Arkin Tikku · 2025
Read Classical Estimation of the Free Energy and Quantum Gibbs Sampling from the Markov Entropy Decomposition by Samuel O. Scalet, Angela Capel, Anirban N. Chowdhury, Hamza Fawzi, Omar Fawzi, Isaac H. Kim, Arkin Tikku (2025) 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-2504-17405.txt.
Introduction
Seven researchers wrote a physics paper in two thousand twenty-five on computing the free energy of quantum spin systems with a classical method. Free energy is a central quantity in physics, but exact values for quantum lattices are out of reach. An older relaxation method approximates it by breaking the system into Markov pieces.
The authors find when that method is guaranteed to converge: when the effective interaction between regions fades fast enough. They prove the fading for one-dimensional systems at any temperature and for hotter systems under a symmetry condition. The result yields fast approximation algorithms. It also powers a scheme to build a full quantum state from the relaxed solution.
Catalog record
| CREATOR | Samuel O. Scalet, Angela Capel, Anirban N. Chowdhury, Hamza Fawzi, Omar Fawzi, Isaac H. Kim, Arkin Tikku |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 101 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-17405
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Classical Estimation of the Free Energy and Quantum Gibbs Sampling from the Markov Entropy Decomposition Samuel O. Scalet, Angela Capel, Anirban N. Chowdhury, Hamza Fawzi, Omar Fawzi, Isaac H. Kim, Arkin Tikku Abstract We revisit the Markov Entropy Decomposition, a classical convex relaxation algorithm introduced by Poulin and Hastings to approximate the free energy in quantum spin lattices. We identify a sufficient condition for its convergence, namely the decay of the effective interaction. The effective interaction, also known as Hamiltonians of mean force, is a widely established correlation measure, and we show our decay condition in 1D at any temperature as well as in the high-temperature regime under a certain commutativity condition on the Hamiltonian building on existing results. This yields polynomial and quasi-polynomial time approximation algorithms in these settings, respectively. Furthermore, the decay of the effective interaction implies the decay of the conditional mutual information for the Gibbs state of the system. We then use this fact to devise a rounding scheme that maps the solution of the convex relaxation to a global state and show that the scheme can be efficiently implemented on a quantum computer, thus proving efficiency of quantum Gibbs sampling under our assumption of decay of the effective interaction. 1 Introduction Determining thermal equilibrium properties of interacting quantum systems is a foundational yet challenging problem in many-body physics. Computing the free energy, or sampling from the equilibrium Gibbs distribution of a quantum Hamiltonian are known to be computationally hard in the worst-case. Therefore, it is important to identify instances where these problems can be solved efficiently and indeed design new algorithmic techniques for doing so. Recent years have seen a number of advances in this area, which have built upon deep insights into the structural properties of thermal states [ 2 ] . One such technique, known as the Markov Entropy Decomposition (MED), was proposed by Poulin and Hastings in [ 69 ] . This algorithm extends ideas from convex optimization for bounding from below ground state energies [ 35 , 14 , 64 , 46 ] to the setting of thermal states, thereby naturally providing lower bounds to the free energy. The MED has been studied numerically [ 32 ] but there are no known guarantees on its convergence. The authors in [ 69 ] conjecture that its convergence is connected to the approximate saturation of strong subadditivity also known as the decay of the conditional mutual information (CMI) . In this paper, we provide a sufficient condition for efficient convergence of the MED - that of an exponentially decaying effective interaction. The effective interaction is the difference between the parent Hamiltonian of marginals of the thermal state (the effective Hamiltonian) and the original Hamiltonian restricted to the support. The effective Hamiltonian, which is also known as the Hamiltonian of mean force, has been widely studied in statistical and quantum many-body physics [ 2 , 78 , 15 , 60 , 10 , 24 , 41 , 81 , 11 ] . Using known results, the exponential decay of the effective interaction with distance can be shown to hold in one-dimensional systems [ 60 ] and for higher-dimensional systems above a threshold temperature under an additional commutativity condition [ 11 ] . We thus prove that the MED gives efficient algorithms in these settings. It is also related to the entanglement Hamiltonian which has been studied in the context of entanglement properties of ground states [ 72 , 26 , 67 , 65 , 25 , 56 , 84 ] . We carefully formalize the notion of an exponentially-decaying effective interaction in a way that is consistent with known rigorous, conjectured and experimental results, and show that this implies the decay of CMI. 1D systems of commuting Hamiltonians fulfill this property even exactly for a finite length scale. As mentioned earlier, it is known to hold for 1D Hamiltonians and for certain commuting systems in higher dimensions at high temperatures. It remains an open question how to generalize this property to noncommuting Hamiltonians beyond 1D since a claimed proof in [ 58 ] was found to be flawed. Our work can be seen as rigorously connecting the efficiency of algorithms for free energies (and thereby expectation values of local observables) to an established physical and information theoretic criterion. Our work also highlights the use of convex programming relaxations in designing provably efficient algorithms for free energy problems. Convex and semi-definite relaxations have been widely used for ground-state energy problems [ 35 , 14 , 64 , 46 ] . Recent work has also extended its use to free energies through ideas similar to the MED [ 13 ] ; see also [ 71 ] for related classical work. However, these approaches typically give algorithms that obtain constant-factor multiplicative approximations to the objective in polynomial time. Our work establishes significantly stronger error guarantees for the convex relaxation considered here — in the two known cases where the exponential decay of the effective interaction holds, the MED has runtime that is (quasi-)polynomial in the inverse error. Effective interaction Quasi-local decomposition of \log(\rho_A) , see Definition 2 . Decay CMI asddd I(A:C|B)\leq e^{-\mathcal{O}(d(A,C))} MED Classical (quasi-)polynomial time algorithm for F and \rho_{A} . Efficient Gibbs sampling (Quasi-)polynomial time quantum algorithm to prepare \rho . Lemma 1 Corollary 1 Corollary 3 Figure 1: Overview of the connections proven in this work. We prove a decay condition on the effective interaction and use it for the design of classical and quantum algorithms for computing the free energy F . Here, \rho and \rho_{A} denote the Gibbs state and its marginal, respectively, and I(A:C|B)=S(AB)+S(BC)-S(ABC)-S(B) is the von Neumann conditional mutual information. By nature of being a convex relaxation algorithm, the optimization variable in the algorithm does not necessarily correspond to a consistent global state. A natural question is then to find a rounding procedure to obtain a globally consistent state from the locally consistent ones. This idea is central to the study of approximation ratios in combinatorial optimization [ 83 ] . Here, we follow this approach, but the rounding algorithm is a quantum algorithm as it should output a large quantum state. More specifically, we use the approximate marginals returned from the MED approximation to construct a sequence of recovery channels that produces a global state close to the Gibbs state. These maps are based on the rotated Petz recovery map, which was introduced as an explicit construction of a map that occurs in a strengthened data-processing inequality [ 31 , 49 ] . The resulting map turns out to be efficiently implementable , providing an efficient Gibbs sampler in the settings described above. The combination of our classical approximation scheme with our quantum rounding procedure thus neatly combines two known approaches to exploit the Markov property of Gibbs states in algorithm design. It should be noted however that our quantum rounding algorithm can be combined with any classical algorithm that computes approximations of the marginals and is not limited to the MED. The obtained guarantee then depends on the approximation quality of the marginals and on a bound on the decay of the CMI. Outline The remainder of this introduction gives a technical overview of the MED recalling