On the complexity of quantum partition functions
Sergey Bravyi, Anirban Chowdhury, et al.
QIP 2022
The physical properties of a quantum many-body system in thermal equilibrium are determined by its partition function and free energy. Here we study the computational complexity of approximating these quantities for n-qubit local Hamiltonians. First, we report a classical algorithm with poly(n) runtime, which approximates the free energy of a given 2-local Hamiltonian provided that it satisfies a certain denseness condition. Our algorithm contributes to a body of work investigating the hardness of approximation for difficult optimization problems. Specifically, this extends existing efficient approximation algorithms for dense instances of the ground energy of 2-local quantum Hamiltonians and the free energy of classical Ising models. Second, we establish polynomial-time equivalence between the problem of approximating the free energy of local Hamiltonians and several other natural tasks ubiquitous in condensed-matter physics and quantum computing, such as the problem of approximating the number of input states accepted by a polynomial-size quantum circuit. These results suggest that the simulation of quantum many-body systems in thermal equilibrium may precisely capture the complexity of a broad family of computational problems that have 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.
Sergey Bravyi, Anirban Chowdhury, et al.
QIP 2022
Theodore Yoder, Sergey Bravyi, et al.
APS March Meeting 2024
Sergey Bravyi, David Gosset
Commun. Math. Phys.
Sergey Bravyi, David Gosset, et al.
Science