Title: "Negative Quasi-Probability, Contextuality and the Power of Quantum Computation"

 

Abstract: Quantum computers promise dramatic advantages over their classical counterparts, but identifying the source of the power in quantum computing has remained elusive. I will describe a remarkable equivalence between two very old notions of non-classicity, namely the appearance of negative quasi-probability in a Wigner function and the onset of contextuality in hidden variable models of quantum mechanics,  and show that these non-classical features are necessary for achieving universal quantum computation via ‘magic state’ distillation, which is the leading model for experimentally realizing a fault-tolerant quantum computer. In addition to clarifying  conceptual issues about the power of quantum computation, these connections advance the resource framework for quantum computation, which has a number of practical applications, such as characterizing the efficiency and trade-offs between distinct theoretical and experimental schemes for achieving robust quantum computation, and putting bounds on the overhead cost for the classical simulation of quantum algorithms.