Contextuality supplies the magic for Quantum Computation

Quantum computers are poised to deliver a dramatic increase in computational power, which can be used to perform difficult tasks such as simulating molecules for medical research much more efficiently than any current computer. However, it is notoriously difficult to characterize what is needed for a quantum computer to be useful. In this paper we prove that two characteristic quantum phenomena, namely, negative probabilities and contextuality, are equivalent in the most well-known and promising architecture for fault-tolerant quantum computation using $d$-level quantum systems ($d$ odd prime). Together with recent work, this implies that contextuality is necessary for quantum computers based upon this architecture to outperform any current computer. Our results are also relevant to the question of identifying the largest ``classical'' subtheory of quantum mechanics.