by Dr. Anirban Narayan Choudhury Institute for Quantum Computing and the Department of Combinatorics and Optimization, University of Waterloo

Abstract:

Interacting quantum many-body systems can exhibit a rich variety of interesting physical phenomena. But studying the properties of many-body systems can be computationally difficult. Tools from theoretical computer science enable us to characterize the computational complexity of physical problems. The application of these tools to quantum many-body systems is the domain of Hamiltonian complexity. A seminal result due to Kitaev showed that approximating the ground-state energy of general quantum spin Hamiltonians within a given error is hard even for quantum computers. Since then, a long line of research has established similar hardness results for various families of Hamiltonians and also for estimating other ground-state properties. However, surprisingly little is known about the problem of approximating thermal equilibrium properties of quantum many-body systems. In this talk, I will present results regarding the computational complexity of approximately computing the partition function of quantum many-body systems.  Firstly, I will show that the problem of approximating quantum partition functions is formally equivalent in computational difficulty to three other problems. These include the problem of estimating the density of states, estimating observables in the thermal state and lastly a quantum analog of an approximate counting task well-known in classical computer science. This gives evidence that the problem of approximating the quantum partition function defines a new computational complexity class. 

Secondly, I will present a new efficient approximation algorithm for the free energy for a family of "dense" Hamiltonians e.g., systems of spins with all-to-all interactions. This algorithm is based on the variational characterization of the free energy: the main idea is to solve a "relaxed" convex optimization program over sets of reduced density matrices and then show that this in fact gives a good approximation to the free energy.

Based on Nat. Phys. 18 (11) 1367–1370 (2022). Joint work with Sergey Bravyi, David Gosset and Pawel Wocjan. arXiv: https://arxiv.org/abs/2110.15466