Skip to Content

Approximation algorithms for bounded-degree local hamiltonians

Computing many-body ground state energies and resolving electronic structure calculations are fundamental problems for fields such as quantum chemistry or condensed matter. Several quantum computing algorithms that address these problems exist, although it is often challenging to establish rigorous bounds on their performances. I shall first consider the general task of approximating the ground state energy of quantum Hamiltonians on bounded-degree graphs. I will discuss our approach to go beyond product state approximations for a quantum analog of the Max Cut problem, where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg interactions between qubits. We provide an efficient classical algorithm which achieves an approximation ratio of at least 0.53 in the worst case - and more recent work by others has improved on this strategy further. We also show that for any instance defined by a 3 or 4-regular graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state (larger even than its semidefinite programming relaxation). Then, I will describe our more recent work to generalize this approach to other bounded-degree local Hamiltonians, where we describe a family of shallow quantum circuits that can be used to improve the approximation ratio achieved by a given product state. Finally, I will discuss results demonstrating the performance of these algorithms via numerical experiments on a 2-dimensional Hubbard model, starting from a checkerboard product state, as well as on some chemistry Hamiltonians, using the Hartree-Fock state as reference. In both cases, we show that the approximate energies produced are close to the exact ones. These algorithms provide a way to systematically improve the estimation of ground state energies and can be used stand-alone or in conjunction with existing quantum algorithms for ground states.

This work is the result of a series of collaborations with David Gosset, Anurag Anshu, Mehdi Soleimanifar, Kenny Choo, and Antonio Mezzacapo and associated publications can be found on arXiv: arXiv:2003.14394, arXiv:2105.01193, arXiv:2111.08090

In the second part of this presentation, I will discuss how I arranged these collaborations outside of my own field, my experience as a visiting graduate researcher at the Waterloo Institute for Quantum Computing, and my subsequent internships at a start-up called 1QBit, and later at IBM. 

Video Talk

Host: Dvira Segal
Event series  CQIQC SeminarsQO/AMO Seminars