We will prove that all states exhibit state-dependent contextuality with respect to stabilizer measurements. Our definition of stabilizer measurement is quite inclusive; we allow all projective measurements wherein elements are rank-1 projectors onto stabilizer states. Rearranging the definition of Ar given in equation (8) gives that is, the set of projectors is a set of projectors whose sum, Σr, is such that: The left-hand side of this equivalence is a witness for contextuality if and only if the independence number of the associated graph Γr satisfies α(Γr) = p as in equation (3). In fact, this simple construction fails to identify any quantum states as contextual because Tr(Σρ) ≤ α(Γr) for all ρ. This is not surprising, given that every single-qudit stabilizer projector is part of exactly one context, namely the basis (one of the complete set of mutually unbiased bases) in which it is contained.

Stabilizer projectors appear in multiple contexts only when two or more subsystems are involved. Consequently, we introduce two-qudit stabilizer projectors such that the structure of Ar as in equation (11) is reflected on the first qudit only. We can limit consideration to two-qudit projectors since this approach characterizes as contextual all single-qudit states that do not have an NCHV model via the discrete Wigner function, that is, we find two-qudit projectors are sufficient to achieve the best possible result.

Our construction uses a different set of projectors for each facet Ar. For a fixed facet Ar, we define a set of separable projectors that is, we take the p(p2 − 1) separable projectors consisting of all tensor products of projectors in equation (11) for the first qudit and computational basis states for the second qudit. We also define the set {Π} ent to be the set of all two-qudit entangled projectors.

The sum of the combined set of separable and entangled projectors is so that for any state of the second system (even the maximally mixed state) we have: Forming the exclusivity graph Γr of {Π}r and applying the results of refs 31 and 32 identifies the left-hand side of equation (15) as a witness for the contextuality of ρ. The following theorem shows that the inequality on the left-hand side of equation (15) is indeed a non-contextuality inequality.

Theorem 1. The independence number of the exclusivity graph associated with Σr is α(Γr) = p3 for all and all prime p ≥ 2. Furthermore, for p > 2, a state exhibits contextuality if and only if it violates one of our non-contextuality inequalities and maximally contextual states saturate the bound on contextuality associated with post-quantum generalized probabilistic theories, that is, Theorem 1 says that, relative to our construction, exactly the states are those that exhibit contextuality. For qudits of odd prime dimension there does not exist any construction using stabilizer measurements that characterizes any as contextual, so that the conditions for contextuality and the possibility of quantum speed-up via MSD coincide exactly.

Proof. For p = 2, a software package43 can be used to obtain: The exclusivity graph Γr and an independent set of 8 vertices is depicted in Fig. 2. The maximal violation of our non-contextuality inequality is achieved by the state |T〉〈T| σ, where |T〉 is the magic state introduced in ref. 14 and σ is arbitrary.

Figure 2: Our construction applied to two qubits. Each of the 30 vertices in this graph Γ corresponds to a two-qubit stabilizer state; connected vertices correspond to orthogonal states. A maximum independent set (representing mutually non-orthogonal states) of size α(Γ) = 8 is highlighted in red. As described in Theorem 1 (main text), this value of α identifies all states as exhibiting contextuality with respect to the stabilizer measurements in our construction. Full size image Download PowerPoint slide

For p > 2, we will now show that . To do this, we use the graph theoretical inequality where is the clique cover number, which is the minimum number of cliques needed to cover every vertex of Γ. (A clique is a subset of a graph’s vertices wherein every pair of vertices is connected.) The clique cover number cannot be greater than the number of distinct bases in {Π}r, which contains p + 1 separable bases and p3 − p entangled bases. Therefore . Then, since there exist40 quantum states ρ such that Tr(Arρ) = −1, by equation (15) and so .

The statement that no non-contextuality inequality constructed from stabilizer measurements can be violated by any state for odd prime dimensions follows from the existence of a NCHV model, namely, the discrete Wigner function35,40,41,42, for all stabilizer measurements and states .

We defer the proof that α(Γr) = p3 to Supplementary Information.