On the complexity of quantum partition functions

Abstract

The partition function and free energy of a quantum many-body system determine its physical properties in thermal equilibrium. Here we study the computational complexity of approximating these quantities for $n$-qubit local Hamiltonians. First, we report a classical algorithm with $\mathrm{poly}(n)$ runtime which approximates the free energy of a given $2$-local Hamiltonian provided that it satisfies a certain denseness condition. Our algorithm combines the variational characterization of the free energy and convex relaxation methods. It contributes to a body of work on efficient approximation algorithms for dense instances of optimization problems which are hard in the general case, and can be viewed as simultaneously extending existing algorithms for (a) the ground energy of dense $2$-local Hamiltonians, and (b) the free energy of dense classical Ising models. Secondly, we establish polynomial-time equivalence between the problem of approximating the free energy of local Hamiltonians and three other natural quantum approximate counting problems, including the problem of approximating the number of witness states accepted by a QMA verifier. These results suggest that simulation of quantum many-body systems in thermal equilibrium may precisely capture the complexity of a broad family of computational problems that has yet to be defined or characterized in terms of known complexity classes. Finally, we summarize state-of-the-art classical and quantum algorithms for approximating the free energy and show how to improve their runtime and memory footprint.

48 pages, 1 figure; v2 fixes a bug in the proof of Theorem 7. This was already fixed in the published version

Cited by in corpus (19)

• Challenges and Opportunities in Quantum Optimization
• Thermal State Preparation via Rounding Promises
• Quantum many-body systems in thermal equilibrium
• On the Sample Complexity of Quantum Boltzmann Machine Learning
• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Certified algorithms for equilibrium states of local quantum Hamiltonians
• Continuous-variable quantum state designs: theory and applications
• Quantum thermodynamics of nonequilibrium processes in lattice gauge theories
• Robust Extraction of Thermal Observables from State Sampling and Real-Time Dynamics on Quantum Computers
• Clique Homology is QMA1-hard
• Algorithmic Cluster Expansions for Quantum Problems
• Projective toric designs, quantum state designs, and mutually unbiased bases
• Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
• Randomized semi-quantum matrix processing
• Lindblad engineering for quantum Gibbs state preparation under the eigenstate thermalization hypothesis
• Efficient learning of ground & thermal states within phases of matter
• A Faster Algorithm for the Free Energy in One-Dimensional Quantum Systems
• High-temperature partition functions and classical simulatability of long-range quantum systems
• Critical Scaling of the Quantum Wasserstein Distance