Abstract
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
arXiv:1909.11485
arXiv:1910.08980