Speaker: Sergey Bravyi, IBM T.J. Watson Research Center

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.