PIRSA:18110100

From estimation of quantum probabilities to simulation of quantum circuits

Pashayan, H. (2018). From estimation of quantum probabilities to simulation of quantum circuits. Perimeter Institute. https://pirsa.org/18110100

Pashayan, Hakop. From estimation of quantum probabilities to simulation of quantum circuits. Perimeter Institute, Nov. 28, 2018, https://pirsa.org/18110100 

          @misc{ pirsa_PIRSA:18110100,
            doi = {10.48660/18110100},
            url = {https://pirsa.org/18110100},
            author = {Pashayan, Hakop},
            keywords = {Quantum Information},
            language = {en},
            title = {From estimation of quantum probabilities to simulation of quantum circuits},
            publisher = {Perimeter Institute},
            year = {2018},
            month = {nov},
            note = {PIRSA:18110100 see, \url{https://pirsa.org}}
          }

Hakop Pashayan Freie Universität Berlin

DOI 10.48660/18110100
Collection
Talk Type Scientific Series
Subject

Abstract

We show that there are two distinct obstacles to an efficient
classical simulation of a general quantum circuit. The first obstacle, which
has been well-studied, is the difficulty of efficiently estimating the
probability associated with a particular measurement outcome. We show that
this alone does not determine whether a quantum circuit can be efficiently
simulated. The second obstacle is that, in general, there can be an
exponential number of `relevant' outcomes that are needed for an accurate
simulation, and so efficient simulation may not be possible even in
situations where the probabilities of individual outcomes can be efficiently
estimated. We show that these two obstacles are distinct, overcoming the
former obstacle being necessary but not sufficient for simulability whilst
overcoming the pair is jointly sufficient for simulability. Specifically, we
prove that a family of quantum circuits is efficiently simulable if it
satisfies two properties: one related to the efficiency of Born rule
probability estimation, and the other related to the sparsity of the outcome
distribution. We then prove a pair of hardness results (using standard
complexity assumptions and a variant of a commonly-used average case
hardness conjecture), where we identify families of quantum circuits that
satisfy one property but not the other, and for which efficient simulation
is not possible. To prove our results, we consider a notion of simulation of
quantum circuits that we call epsilon-simulation. This notion is less
stringent than exact sampling and is now in common use in quantum hardness
proofs.