- Home »
- From estimation of quantum probabilities to simulation of quantum circuits

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.

Collection/Series:

Event Type:

Seminar

Scientific Area(s):

Speaker(s):

Event Date:

Wednesday, November 28, 2018 - 16:00 to 17:30

Location:

Bob Room

Room #:

405

©2012 Perimeter Institute for Theoretical Physics