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:2506.06869

Memory cost of quantum contextuality with Pauli observables

Stefan Trandafir, Colm Kelleher, Adán Cabello

Published Jun 7, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2506.06869

Related papers

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

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

Optimal Classical Simulation of State-Independent Quantum Contextuality

Adán Cabello, Mile Gu, Otfried Gühne +1 more

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.

arXiv:1709.07372•Physical Review Letters•Mar 27, 2018•38 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

The memory cost of simulating two-qubit Pauli contextuality under repeatability and product rules is exactly log2(5) bits

Brent W. Jonah

For the 15 two-qubit Pauli observables, any classical Mealy machine reproducing the quantum predictions (Ia) repeatability and (II) context product rules requires exactly log2(5) ≈ 2.32 bits of memory. Upper bound: an explicit five-state machine, verified including the intervening-measurement form of (Ia). Lower bound: machine-certified unsatisfiability at four states (three independent encodings × three SAT solvers; DRUP proof checked by drat-trim; byte-reproducible formula; preregistrations externally timestamped before computation). This closes the gap [log2 4, log2 6] left open in arXiv:2506.06869. A verified note documents 338 pairwise-inequivalent optimal machines collapsing to 19 output-atlas orbits under the target-preserving affine symmetry group of order 23,040. Verification: unzip the deposit, run python3 verifier3.py (537 assertions, ~30 s, stdlib only), then drat-trim E2_n4.cnf E2_n4_unsat_glucose.drup (prints s VERIFIED).

•Jul 14, 2026•0 citations
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.
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.
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.
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.
For the 15 two-qubit Pauli observables, any classical Mealy machine reproducing the quantum predictions (Ia) repeatability and (II) context product rules requires exactly log2(5) ≈ 2.32 bits of memory. Upper bound: an explicit five-state machine, verified including the intervening-measurement form of (Ia). Lower bound: machine-certified unsatisfiability at four states (three independent encodings × three SAT solvers; DRUP proof checked by drat-trim; byte-reproducible formula; preregistrations externally timestamped before computation). This closes the gap [log2 4, log2 6] left open in arXiv:2506.06869. A verified note documents 338 pairwise-inequivalent optimal machines collapsing to 19 output-atlas orbits under the target-preserving affine symmetry group of order 23,040. Verification: unzip the deposit, run python3 verifier3.py (537 assertions, ~30 s, stdlib only), then drat-trim E2_n4.cnf E2_n4_unsat_glucose.drup (prints s VERIFIED).