Contextuality and the Single-Qubit Stabilizer Subtheory

Contextuality is a fundamental nonclassical property of quantum theory, which has recently been proven to be a key resource for achieving quantum speed-ups in some leading models of quantum computation. However, which of the forms of contextuality, and how much thereof, are required to obtain a speed-up in an arbitrary model of quantum computation remains unclear. In this Letter, we show that the relation between contextuality and a computational advantage is more complicated than previously thought. We achieve this by proving that generalized contextuality is present even within the simplest subset of quantum operations, the so-called single-qubit stabilizer theory, which offers no computational advantage and was previously believed to be completely noncontextual. However, the contextuality of the single-qubit stabilizer theory can be confined to transformations. Therefore, our result also demonstrates that the commonly considered prepare-and-measure scenarios (which ignore transformations) do not fully capture the contextuality of quantum theory.