Simulating quantum contextuality with classical systems requires memory. A fundamental yet open question is which 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 classical systems need to simulate arbitrary QSIC sets 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 \approx 4.585$ bits, simulating a single qutrit tested with the Yu-Oh set requires, at least, $5.740$ bits.
Submitted 21 Sep 2017 to Quantum Physics
Published 22 Sep 2017
Author comments: 6 pages, 4 figureshttp://arxiv.org/abs/1709.07372http://arxiv.org/pdf/1709.07372.pdf