Optimal Classical Simulation of State-Independent Quantum Contextuality

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₂24≈4.585 bits, simulating a single qutrit tested with the Yu-Oh set requires, at least, 5.740 bits.