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.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, 201155 citations

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.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.06869Jun 7, 20250 citations

Contextuality bounds the efficiency of classical simulation of quantum processes

Angela Karanjai, Joel J. Wallman, Stephen D. Bartlett

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.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:1802.07744Feb 21, 201820 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.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.07372Physical Review LettersMar 27, 201838 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.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.3561AIP conference proceedingsJan 1, 201217 citations

Memory cost of quantum protocols

Alessandro Bisio, Giacomo Mauro D’Ariano, Paolo Perinotti +1 more

We consider the problem of minimizing the ancillary systems required to realize an arbitrary strategy of a quantum protocol, with the assistance of classical memory. For this purpose we introduce the notion of memory cost of a strategy to measure the resources required in terms of ancillary dimension. We provide a condition for the cost to be equal to a given value, and we use this result to evaluate the cost in some special cases. As an example, we show that any covariant protocol for the cloning of a unitary transformation requires at most one ancillary qubit. We also prove that the memory cost has to be determined globally and cannot be calculated by optimizing the resources independently at each step of the strategy.We consider the problem of minimizing the ancillary systems required to realize an arbitrary strategy of a quantum protocol, with the assistance of classical memory. For this purpose we introduce the notion of memory cost of a strategy to measure the resources required in terms of ancillary dimension. We provide a condition for the cost to be equal to a given value, and we use this result to evaluate the cost in some special cases. As an example, we show that any covariant protocol for the cloning of a unitary transformation requires at most one ancillary qubit. We also prove that the memory cost has to be determined globally and cannot be calculated by optimizing the resources independently at each step of the strategy.

arXiv:1112.3853Physical Review AMar 30, 20125 citations

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.