title: Contextuality supplies the 'magic' for quantum computation.
abstract: Quantum computers promise dramatic advantages over their classical counterparts, but the source of the power in quantum computing has remained elusive. Here we prove a remarkable equivalence between the onset of contextuality and the possibility of universal quantum computation via 'magic state' distillation, which is the leading model for experimentally realizing a fault-tolerant quantum computer. This is a conceptually satisfying link, because contextuality, which precludes a simple 'hidden variable' model of quantum mechanics, provides one of the fundamental characterizations of uniquely quantum phenomena. Furthermore, this connection suggests a unifying paradigm for the resources of quantum information: the non-locality of quantum theory is a particular kind of contextuality, and non-locality is already known to be a critical resource for achieving advantages with quantum communication. In addition to clarifying these fundamental issues, this work advances 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.
authors.affiliation: 1] Department of Mathematical Physics, National University of Ireland, Maynooth, Ireland [2] Institute for Quantum Computing and Department of Applied Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada.
authors.forename: Mark
authors.initials: M
authors.lastname: Howard
authors.affiliation: Institute for Quantum Computing and Department of Applied Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada.
authors.forename: Joel
authors.initials: J
authors.lastname: Wallman
authors.affiliation: 1] Institute for Quantum Computing and Department of Applied Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada [2] Department of Statistics, University of Toronto, 100 St George Street, Toronto, Ontario M5S 3G3, Canada.
authors.forename: Victor
authors.initials: V
authors.lastname: Veitch
authors.affiliation: Institute for Quantum Computing and Department of Applied Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada.
authors.forename: Joseph
authors.initials: J
authors.lastname: Emerson