Spring 2020

Classical Algorithms for Quantum Mean Values

Thursday, May 7th, 2020 10:00 am10:50 am

Add to Calendar


Sergey Bravyi (IBM T.J. Watson Research Center)


Quantum mean value problem is the task of estimating the expected value of a tensor product observable
on the output state of a quantum circuit. This task is a common step of NISQ era quantum algorithms such as VQE or QAOA. I will consider the complexity of the quantum mean value problem as a function of circuit depth, qubit connectivity, and the structure of observables to be measured. Polynomial-time classical algorithms are described solving the quantum mean value problem in two special cases:
(a) 2D constant-depth variational circuits relevant for VQE,
(b) level-1 and level-2 QAOA circuits associated with graph-based optimization problems.
As an application, I will describe a classical simulation of the recently proposed Recursive QAOA
algorithm applied to graph coloring problems.

Based on

PDF icon Talk Slides2.57 MB