Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1709.07372 · Physical Review Letters

Optimal Classical Simulation of State-Independent Quantum Contextuality

Adán Cabello, Mile Gu, Otfried Gühne, Zhen‐Peng Xu

Published Mar 27, 2018• 38 citations
arXivHTMLPDF

Abstract

Simulating quantum contextuality with classical systems requires memory. A fundamental yet open question is what is the minimum memory needed and, therefore, the precise sense in which quantum systems outperform classical ones. Here, we make rigorous the notion of classically simulating quantum state-independent contextuality (QSIC) in the case of a single quantum system submitted to an infinite sequence of measurements randomly chosen from a finite QSIC set. We obtain the minimum memory needed to simulate arbitrary QSIC sets via classical systems under the assumption that the simulation should not contain any oracular information. In particular, we show that, while classically simulating two qubits tested with the Peres-Mermin set requires log_{2}24≈4.585 bits, simulating a single qutrit tested with the Yu-Oh set requires, at least, 5.740 bits.

DOI
10.1103/physrevlett.120.130401

Related papers

Memory cost of quantum contextuality with Pauli observables

Stefan Trandafir, Colm Kelleher, Adán Cabello

Classically simulating the quantum contextual correlations produced by sequences of ideal measurements of compatible observables requires the measured system to have an internal memory. Computing the minimum amount of memory needed is, in general, challenging. Here, building upon the work of Kleinmann et al. [New J. Phys. 13, 113011 (2011)], we prove that the memory cost for simulating the contextuality produced by the $10$ three-qubit observables of Mermin's pentagram is only $\log_2(5) \approx 2.32$ bits, but the memory cost for simulating the contextuality produced by all $15$ two-qubit Pauli observables is, at least, $\log_2(6) \approx 2.58$ bits, thus exceeding the classical capacity of the system on which the measurements are performed. We also add results on the memory for simulating some subsets of quantum predictions.

arXiv:2506.06869•Jun 7, 2025•0 citations

Memory cost of quantum contextuality

Matthias Kleinmann, Otfried Gühne, José R Portillo +2 more

The simulation of quantum effects requires certain classical resources, and quantifying them is an important step to characterize the difference between quantum and classical physics. For a simulation of the phenomenon of state-independent quantum contextuality, we show that the minimum amount of memory used by the simulation is the critical resource. We derive optimal simulation strategies for important cases and prove that reproducing the results of sequential measurements on a two-qubit system requires more memory than the information-carrying capacity of the system.

arXiv:1007.3650•New Journal of Physics•Nov 9, 2011•74 citations

Memory cost for simulating all quantum correlations from the Peres–Mermin scenario

Gabriel Fagundes, Matthias Kleinmann

Abstract Sequences of compatible quantum measurements can be contextual and any simulation with a classical model conforming with the quantum predictions needs to use internal memory. Kleinmann et al (2011 New J. Phys . 13 113011) showed that simulating sequences from the Peres–Mermin scenario requires at least three different internal states in order not to contradict the deterministic predictions of quantum theory. We extend this analysis to probabilistic quantum predictions and ask how much memory is required to simulate correlations generated for sequences of compatible observables by any quantum state. We find that even in this comprehensive approach only three internal states are required for a perfect simulation of quantum correlations in the Peres–Mermin scenario.

arXiv:1611.07515•Journal of Physics A Mathematical and Theoretical•Jun 21, 2017•23 citations

Memory cost of quantum contextuality

Cabello Quintero, Adán, Otfried Gühne, Matthias Kleinmann +2 more

The simulation of quantum effects requires certain classical resources, and quantifying them is an important step to characterize the difference between quantum and classical physics. For a simulation of the phenomenon of state-independent quantum contextuality, we show that the minimum amount of memory used by the simulation is the critical resource. We derive optimal simulation strategies for important cases and prove that reproducing the results of sequential measurements on a two-qubit system requires more memory than the information-carrying capacity of the system.

•Jan 1, 2011•55 citations

A contextual extension of Spekkens' toy model

Jan-Åke Larsson

Quantum systems show contextuality.More precisely, it is impossible to reproduce the quantum-mechanical predictions using a non-contextual realist model, i.e., a model where the outcome of one measurement is independent of the choice of compatible measurements performed in the measurement context.There has been several attempts to quantify the amount of contextuality for specific quantum systems, for example, in the number of rays needed in a KS proof, or the number of terms in certain inequalities, or in the violation, noise sensitivity, and other measures.This paper is about another approach: to use a simple contextual model that reproduces the quantum-mechanical contextual behaviour, but not necessarily all quantum predictions.The amount of contextuality can then be quantified in terms of additional resources needed as compared with a similar model without contextuality.In this case the contextual model needs to keep track of the context used, so the appropriate measure would be memory.Another way to view this is as a memory requirement to be able to reproduce quantum contextuality in a realist model.The model we will use can be viewed as an extension of Spekkens' toy model [Phys.Rev. A 75, 032110 (2007)], and the relation is studied in some detail.To reproduce the quantum predictions for the Peres-Mermin square, the memory requirement is more than one bit in addition to the memory used for the individual outcomes in the corresponding noncontextual model.

arXiv:1111.3561•AIP conference proceedings•Jan 1, 2012•17 citations

How Quantum Contextuality disappears in the Classical Limit

Arthur C. R. Dutra, Roberto D. Baldijão, Marcelo Terra Cunha

The emergence of classicality is fundamentally driven by the interaction between a quantum system and its environment. Foundational open-system approaches, notably the Caldeira-Leggett model, successfully captured how these interactions lead to macroscopic effects like quantum dissipation and decoherence. However, these approaches often leave the precise definitions of classicality and quantumness ambiguous. In quantum information theory, this boundary is a heavily scrutinized question, and Kochen-Specker contextuality emerges as a hallmark of nonclassicality. It is therefore natural to investigate whether decoherence can actually suppress this property. Taking this path creates an apparent conundrum, once there exist two distinct manifestations of quantum contextuality: state-dependent and state-independent ones. While state-dependent contextuality naturally vanishes under state degradation, state-independent contextuality could persist for any quantum state, since it shows up even for the maximally mixed state! In this paper, we resolve this apparent paradox by analyzing sequential measurement implementations of the paradigmatic Klyachko, Can, Binicioğlu, and Shumovsky (KCBS) and Peres-Mermin prepare-and-measure scenarios under the influence of depolarizing channels. By introducing noise both prior to and in between measurements, and by analyzing the resulting sequential correlators in both the Schrödinger and Heisenberg pictures, we show how open-system dynamics suppress the correlations required to witness contextuality, leading to classicalization.

quant-pharXiv:2604.24735•Apr 28, 2026•0 citations
Simulating quantum contextuality with classical systems requires memory. A fundamental yet open question is what is the minimum memory needed and, therefore, the precise sense in which quantum systems outperform classical ones. Here, we make rigorous the notion of classically simulating quantum state-independent contextuality (QSIC) in the case of a single quantum system submitted to an infinite sequence of measurements randomly chosen from a finite QSIC set. We obtain the minimum memory needed to simulate arbitrary QSIC sets via classical systems under the assumption that the simulation should not contain any oracular information. In particular, we show that, while classically simulating two qubits tested with the Peres-Mermin set requires log_{2}24≈4.585 bits, simulating a single qutrit tested with the Yu-Oh set requires, at least, 5.740 bits.
Classically simulating the quantum contextual correlations produced by sequences of ideal measurements of compatible observables requires the measured system to have an internal memory. Computing the minimum amount of memory needed is, in general, challenging. Here, building upon the work of Kleinmann et al. [New J. Phys. 13, 113011 (2011)], we prove that the memory cost for simulating the contextuality produced by the 101010 three-qubit observables of Mermin's pentagram is only log⁡2(5)≈2.32\log_2(5) \approx 2.32log2​(5)≈2.32 bits, but the memory cost for simulating the contextuality produced by all 151515 two-qubit Pauli observables is, at least, log⁡2(6)≈2.58\log_2(6) \approx 2.58log2​(6)≈2.58 bits, thus exceeding the classical capacity of the system on which the measurements are performed. We also add results on the memory for simulating some subsets of quantum predictions.
The simulation of quantum effects requires certain classical resources, and quantifying them is an important step to characterize the difference between quantum and classical physics. For a simulation of the phenomenon of state-independent quantum contextuality, we show that the minimum amount of memory used by the simulation is the critical resource. We derive optimal simulation strategies for important cases and prove that reproducing the results of sequential measurements on a two-qubit system requires more memory than the information-carrying capacity of the system.
Abstract Sequences of compatible quantum measurements can be contextual and any simulation with a classical model conforming with the quantum predictions needs to use internal memory. Kleinmann et al (2011 New J. Phys . 13 113011) showed that simulating sequences from the Peres–Mermin scenario requires at least three different internal states in order not to contradict the deterministic predictions of quantum theory. We extend this analysis to probabilistic quantum predictions and ask how much memory is required to simulate correlations generated for sequences of compatible observables by any quantum state. We find that even in this comprehensive approach only three internal states are required for a perfect simulation of quantum correlations in the Peres–Mermin scenario.
The simulation of quantum effects requires certain classical resources, and quantifying them is an important step to characterize the difference between quantum and classical physics. For a simulation of the phenomenon of state-independent quantum contextuality, we show that the minimum amount of memory used by the simulation is the critical resource. We derive optimal simulation strategies for important cases and prove that reproducing the results of sequential measurements on a two-qubit system requires more memory than the information-carrying capacity of the system.
Quantum systems show contextuality.More precisely, it is impossible to reproduce the quantum-mechanical predictions using a non-contextual realist model, i.e., a model where the outcome of one measurement is independent of the choice of compatible measurements performed in the measurement context.There has been several attempts to quantify the amount of contextuality for specific quantum systems, for example, in the number of rays needed in a KS proof, or the number of terms in certain inequalities, or in the violation, noise sensitivity, and other measures.This paper is about another approach: to use a simple contextual model that reproduces the quantum-mechanical contextual behaviour, but not necessarily all quantum predictions.The amount of contextuality can then be quantified in terms of additional resources needed as compared with a similar model without contextuality.In this case the contextual model needs to keep track of the context used, so the appropriate measure would be memory.Another way to view this is as a memory requirement to be able to reproduce quantum contextuality in a realist model.The model we will use can be viewed as an extension of Spekkens' toy model [Phys.Rev. A 75, 032110 (2007)], and the relation is studied in some detail.To reproduce the quantum predictions for the Peres-Mermin square, the memory requirement is more than one bit in addition to the memory used for the individual outcomes in the corresponding noncontextual model.
The emergence of classicality is fundamentally driven by the interaction between a quantum system and its environment. Foundational open-system approaches, notably the Caldeira-Leggett model, successfully captured how these interactions lead to macroscopic effects like quantum dissipation and decoherence. However, these approaches often leave the precise definitions of classicality and quantumness ambiguous. In quantum information theory, this boundary is a heavily scrutinized question, and Kochen-Specker contextuality emerges as a hallmark of nonclassicality. It is therefore natural to investigate whether decoherence can actually suppress this property. Taking this path creates an apparent conundrum, once there exist two distinct manifestations of quantum contextuality: state-dependent and state-independent ones. While state-dependent contextuality naturally vanishes under state degradation, state-independent contextuality could persist for any quantum state, since it shows up even for the maximally mixed state! In this paper, we resolve this apparent paradox by analyzing sequential measurement implementations of the paradigmatic Klyachko, Can, Binicioğlu, and Shumovsky (KCBS) and Peres-Mermin prepare-and-measure scenarios under the influence of depolarizing channels. By introducing noise both prior to and in between measurements, and by analyzing the resulting sequential correlators in both the Schrödinger and Heisenberg pictures, we show how open-system dynamics suppress the correlations required to witness contextuality, leading to classicalization.