CM Seminar - Obstacles to variational quantum simulation and optimization

Abstract
Variational quantum algorithms such as VQE or QAOA aim at simulating low-energy properties of quantum many-body systems or finding approximate solutions of combinatorial optimization problems.
Such algorithms, designed for near-term quantum processors, employ variational states based on low-depth quantum circuits to minimize the expected energy of a Hamiltonian describing the system of interest.
Given the current enthusiasm for variational quantum algorithms, it is natural to question whether or not they can be more powerful than classical algorithms in some sense.
In this talk I will explain how general structural properties of variational states such as locality and symmetry may be used to assess their computational power.
In particular, I will show that variational quantum algorithms based on constant depth circuits with nearest-neighbor gates on a 2D grid of qubits can be simulated classically in linear time.
Furthermore, quantum approximate optimization algorithms based on low-depth circuits fail to achieve advantage over the best known classical optimization algorithm for certain instances of the MAX-CUT problem.

Based on
arXiv:1909.11485
arXiv:1910.08980

Biography
I am a Research Staff Member at the IBM T.J. Watson Research Center.
My research interests focus mainly on quantum algorithms, quantum error correction, and computational complexity theory.
Prior to joining IBM, I spent several years as a postdoc at California Institute of Technology in John Preskill's group.
I obtained my PhD at Landau Institute for Theoretical Physics in 2003.