Quantum computational advantage implies contextuality
Farid Shähandeh · arXiv (Cornell University) · 2021
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.