Joel Wallman, IQC
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 talk I will show that two characteristic quantum phenomena, namely, negative probabilities and contextuality, are equivalent with respect to the stabilizer formalism for qudits (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. I will also discuss how the amount of contextuality quantifies the run time of a concrete simulation algorithm and how our results can be applied to qubits.