Quantum computational advantage implies contextuality

Abstract

We show that a separation between the class of all problems that can efficiently be solved on a quantum computer and those solvable using probabilistic classical algorithms in polynomial time implies the generalized contextuality of quantum algorithms. Our result subsumes versions of Gottesman-Knill theorem as special cases.

6 pages, minor changes incl. a brief comment on the single-qubit contextuality, references added, further comments are encouraged

References in corpus (5)

• Negativity and contextuality are equivalent notions of nonclassicality
• Preparation contextuality powers parity-oblivious multiplexing
• Computational power of correlations
• Quantum computing and the entanglement frontier
• Frame representations of quantum mechanics and the necessity of negativity in quasi-probability representations