From estimation of quantum probabilities to simulation of quantum circuits

Add to your list(s) Download to your calendar using vCal

• Hakop Pashayan
• Thursday 25 January 2018, 14:15-15:15
• CMS, MR6.

If you have a question about this talk, please contact Johannes Bausch.

This talk has been canceled/deleted

We show that there are two distinct aspects of a general quantum circuit that can make it hard to efficiently simulate with a classical computer. The first aspect, which has been well-studied, is that it can be hard to efficiently estimate the probability associated with a particular measurement outcome. However, we show that this aspect alone does not determine whether a quantum circuit can be efficiently simulated. The second aspect 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 aspects are distinct, the former being necessary but not sufficient for simulability whilst 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.

This talk is part of the CQIF Seminar Series series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.