Title: Approximation algorithms for dense quantum Hamiltonians using convex relaxations
| Speaker: | Anirban Chowdhury |
| Affiliation: | University of Waterloo |
| Location: | MC 5479 |
Abstract: Computing ground-state energy and partition functions for quantum Hamiltonian systems are problems of broad applicability in physics. These are also natural generalizations of well-studied classical computational tasks such as maximum constraint satisfaction and computing partition functions of Ising models. In this talk, I will present new classical approximation algorithms for these problems in the case of dense quantum Hamiltonians. Our algorithm builds upon prior work by Risteski for approximating partition functions for Ising models on densely connected graphs, and uses ideas from linear programming relaxations. The main idea is to formulate the computational task as a convex optimization problem, then solve an easier "relaxed" version of the problem, and finally use a rounding argument to show that the relaxed optimization nevertheless gives a good approximation. This talk will be based on joint work with Sergey Bravyi, David Gosset and Pawel Wocjan. Journal reference: Nature Physics 18, 1367–1370 (2022).