Contextuality bounds the efficiency of classical simulation of quantum processes

Abstract

Contextuality has been conjectured to be a super-classical resource for quantum computation, analogous to the role of non-locality as a super-classical resource for communication. We show that the presence of contextuality places a lower bound on the amount of classical memory required to simulate any quantum sub-theory, thereby establishing a quantitative connection between contextuality and classical simulability. We apply our result to the qubit stabilizer sub-theory, where the presence of state-independent contextuality has been an obstacle in establishing contextuality as a quantum computational resource. We find that the presence of contextuality in this sub-theory demands that the minimum number of classical bits of memory required to simulate a multi-qubit system must scale quadratically in the number of qubits; notably, this is the same scaling as the Gottesman-Knill algorithm. We contrast this result with the (non-contextual) qudit case, where linear scaling is possible.

arXiv comment6 pages, comments welcome

References in corpus (15)

• Improved Simulation of Stabilizer Circuits
• On the reality of the quantum state
• Contextuality for preparations, transformations, and unsharp measurements
• Contextuality supplies the magic for quantum computation
• Graph-Theoretic Approach to Quantum Correlations
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Computational power of correlations
• Contextuality as a resource for models of quantum computation on qubits
• Reconstruction of Gaussian quantum mechanics from Liouville mechanics with an epistemic restriction
• No $\psi$-epistemic model can fully explain the indistinguishability of quantum states
• Contextuality and Wigner function negativity in qubit quantum computation
• Maximally epistemic interpretations of the quantum state and contextuality
• $\psi$-epistemic models are exponentially bad at explaining the distinguishability of quantum states
• Representing probabilistic data via ontological models

Cited by in corpus (14)

• Enhancing Generative Models via Quantum Correlations
• Phase space simulation method for quantum computation with magic states on qubits
• Contextuality as a resource for measurement-based quantum computation beyond qubits
• Resource theory of contextuality for arbitrary prepare-and-measure experiments
• Classical Simulation of Noncontextual Pauli Hamiltonians
• Noncontextuality Inequalities from Antidistinguishability
• Using a resource theoretic perspective to witness and engineer quantum generalized contextuality for prepare-and-measure scenarios
• $\psi$-epistemic interpretations of quantum theory have a measurement problem
• Corrected Bell and Noncontextuality Inequalities for Realistic Experiments
• Contextuality without access to a tomographically complete set
• Closing Bell: Boxing black box simulations in the resource theory of contextuality
• From the problem of Future Contingents to Peres-Mermin square experiments: An introductory review to Contextuality
• Classical Limits and Contextuality in a Scenario of Multiple Observers
• Quantum formalism on the plane: POVM-Toeplitz quantization, Naimark theorem and linear polarisation of the light