15626

Video URL

https://simons.berkeley.edu/talks/classical-algorithms-quantum-mean-values-0

Classical Algorithms for Quantum Mean Values

(2020). Classical Algorithms for Quantum Mean Values. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/classical-algorithms-quantum-mean-values-0

Classical Algorithms for Quantum Mean Values. The Simons Institute for the Theory of Computing, May. 07, 2020, https://simons.berkeley.edu/talks/classical-algorithms-quantum-mean-values-0 

          @misc{ scivideos_15626,
            doi = {},
            url = {https://simons.berkeley.edu/talks/classical-algorithms-quantum-mean-values-0},
            author = {},
            keywords = {},
            language = {en},
            title = {Classical Algorithms for Quantum Mean Values},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {may},
            note = {15626 see, \url{https://scivideos.org/Simons-Institute/15626}}
          }
Sergey Bravyi (IBM T.J. Watson Research Center)
Talk number15626
Source RepositorySimons Institute
Subject

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