COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > CQIF Seminar Series > From estimation of quantum probabilities to simulation of quantum circuits

## From estimation of quantum probabilities to simulation of quantum circuitsAdd 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. |
## Other listsMeeting the Challenge of Healthy Ageing in the 21st Century Research Seminars - Department of Biochemistry Cambridge Post-Conflict and Post-Crisis Group## Other talksSummer Cactus & Succulent Show Building cortical networks: from molecules to function Disabled Academics in the 21st Century: 15th Annual Disability Lecture The MHC ligandome of two contagious cancers within the Tasmanian devil population, Devil Facial Tumour 1 and Devil Facial Tumour 2 The genetic framework of germline stem cell development My Life in Science Seminar â€œPublishing in Science: an Inside Look" |