Quantum computational advantage implies contextuality
arXiv:2112.00024
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.
arXiv comment6 pages, minor changes incl. a brief comment on the single-qubit contextuality, references added, further comments are encouraged
References in corpus (22)
- Quantum entanglement
- Efficient classical simulation of slightly entangled quantum computations
- Quantum Coherence as a Resource
- Measurement-based quantum computation with cluster states
- Contextuality supplies the magic for quantum computation
- Positive Wigner functions render classical simulation of quantum computation efficient
- Efficient Classical Simulation of Continuous Variable Quantum Information Processes
- Quantum advantage with shallow circuits
- Negativity and contextuality are equivalent notions of nonclassicality
- Most quantum states are too entangled to be useful as computational resources
- Contextuality in Measurement-based Quantum Computation
- Preparation contextuality powers parity-oblivious multiplexing
- Computational power of correlations
- Quantum computing and the entanglement frontier
- Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
- Contextuality as a resource for models of quantum computation on qubits
- Frame representations of quantum mechanics and the necessity of negativity in quasi-probability representations
- Contextuality and Wigner function negativity in qubit quantum computation
- Contextuality as a resource for measurement-based quantum computation beyond qubits
- Contextuality of general probabilistic theories
- The whole is greater than the sum of the parts: on the possibility of purely statistical interpretations of quantum theory
- The ontological identity of empirical indiscernibles: Leibniz's methodological principle and its significance in the work of Einstein