WorksPhysics and Astronomy
Stabilizer-Restricted Antidistinguishability in Quantum Computation with Magic States
Abstract
An antidistinguishing measurement for a family of preparations excludes at least one preparation for every possible outcome, constraining 'classical' representations of these processes, known as ontological models. We develop this connection within quantum computing with magic states (QCM), a universal model of quantum computation. Our constructions use adaptive Pauli measurements on tensor products of single-qubit non stabilizer states, including families associated with the Clifford hierarchy. These constructions yield stabilizer-restricted versions of the Pusey-Barrett-Rudolph theorem: any ontological model reproducing these measurement statistics and satisfying preparation independence must assign disjoint ontic supports to the preparations considered. We demonstrate this obstruction to preparation independence in a concrete ontological model based on convex polytopes used for the classical simulation of QCM.
Introduction
A central theme in the foundations of quantum theory has been to identify a precise notion of what is meant by ‘classical’. Throughout the development of the subject, a web of such notions has emerged, based on locality [1], noncontextuality [2, 3], its generalized variant [4], or nonnegativity in quasiprobability representations [5, 6]. A common framework for studying these notions describes an underlying physical reality in terms of an ontic state [7]. Quantum theory can be described in operational terms [8], i.e. by preparations, transformations, and measurements, while ontological models represent these operational primitives using probability distributions, transition kernels, and response functions defined on the ontic state space. Additional constraints on the mathematical form of the ontological model encode the relevant notion of classicality, with attendant ‘no-go’ results demonstrating incompatibility with quantum mechanics.
Pusey, Barrett, and Rudolph (PBR) [9] proved a fundamental ‘no-go’ theorem on the nature of the quantum state. Their argument is based on the principle of preparation independence, which reflects the classical intuition that operationally independent preparations should be represented in the ontological model by statistically independent product distributions. The PBR theorem places particular emphasis on the ontological representation of preparations: under preparation independence, distinct pure quantum states must be represented by distributions with disjoint supports. Another key notion is that of antidistinguishability [10, 11]. A quantum measurement is said to be weakly antidistinguishing for a set of states if every measurement outcome has zero probability for at least one preparation in the set [12]. The existence of such a measurement forces the ontological representations of the preparations to have vanishing common overlap. This is precisely the operational ingredient needed to prove the PBR theorem.
Complementary to these foundational developments has been an increased interest in the role of such nonclassical features in quantum computational advantage. Within the setting of measurement-based quantum computation [13], Bell nonlocality and contextuality have been identified as resources for increased computational power relative to classical counterparts [14, 15, 16, 17]. Similarly, negativity in quasiprobability representations quantifies the cost of particular classical simulation schemes [18, 19, 20, 21]. In several settings, contextuality and negativity have been shown to be equivalent notions [22, 23, 24, 25, 26]. By contrast, the computational implications of the PBR theorem and its underlying principle of preparation independence have received less attention; a related connection to classical simulation is developed in [27].
Ontological models also provide a natural framework for studying classical simulation of quantum circuits [27, 28, 29]. A prominent example is the discrete Wigner representation of Gross [30]. Restricted to states with nonnegative Wigner functions and stabilizer operations, it provides a noncontextual ontological model for odd-dimensional qudit systems that includes the stabilizer fragment [23] and facilitates a sampling-based classical simulation scheme [18]. In particular, the Wigner representation respects tensor products, so that independently prepared states with nonnegative Wigner functions are represented by product distributions. This gives a preparation-independent model of the corresponding operational fragment. For states exhibiting negativity, the same tensor-product property enables a multiplicative measure controlling the sampling cost [19].
For qubits, many of these appealing properties of the odd-qudit case do not persist, and understanding these distinctions has been the subject of continued investigation [21, 25, 31, 32, 33, 34]. An important development along these lines was made in [35] with the introduction of a family of geometric structures called Pauli polytopes, also known as polytopes, that are related by duality to the well-known stabilizer polytopes [36]. These objects furnish a concrete -epistemic ontological model that can be used for the classical simulation of quantum computing with magic states (QCM) [37], a universal model of quantum computation. As such, these ontological representations can be rigorously studied using polytope-theoretic methods, potentially yielding insights into the complexity of classical simulation and the boundaries of quantum advantage.
Results and outline
Summary of main results
In this paper we construct families of antidistinguishing measurements using adaptive and nonadaptive multiqubit Pauli measurements applied to preparation families consisting of completely separable states of computational interest, including those arising from the Clifford hierarchy [38]. These preparations and measurements lie within the basic computational primitives of QCM. Our results therefore present a direct operational obstruction for ontological models of QCM that assign overlapping distributions to the state pairs considered: such models cannot both satisfy preparation independence and reproduce the relevant Born-rule statistics. Although stabilizer implementations of particular PBR measurements are already known [9, 27], the general PBR construction does not impose this measurement restriction. Our work extends these stabilizer-restricted arguments to computationally relevant families of non-stabilizer states.
Let us summarize our main results. For the stabilizer fragment, we generalize existing constructions [9, 27] to demonstrate that any pair of distinct nonorthogonal pure stabilizer states yields a PBR proof (Proposition 5.2). A complementary argument based on contextuality appears in Appendix § 11. Additionally, we construct stabilizer-restricted weakly antidistinguishing measurements for magic-state preparations consisting of tensor products drawn from the single-qubit pairs and , where
and labels the non-Clifford levels of the hierarchy [38] (Theorem 6.4). The number of qubits used by our construction scales exponentially with the level of the hierarchy according to . The construction uses an algebraic property of these phase-rotated states: a two-qubit parity measurement maps pairs of such states either to a maximally entangled stabilizer state on the odd-parity branch or to an encoded single-qubit state with phase level reduced by one on the even-parity branch.
It is also possible to construct a stabilizer-restricted PBR proof for every number of qubits (Theorem 6.5). For this, we use the preparation pair
whose angle depends on the number of qubits. The nonadaptive Pauli measurements are specified by the canonical stabilizer generators of the graph state corresponding to , i.e. the complete graph on vertices. Each outcome excludes exactly one preparation in the resulting product family.
The above results hold for otherwise arbitrary ontological models reproducing the specified preparation and Pauli-measurement statistics. We then specialize to the Pauli ontological model, based on the Pauli polytopes introduced in [35]. Within this model, the conceptual issue of preparation independence can be related to a structural question about closure under the operator tensor product. Our construction of antidistinguishing measurements for the -state pair (), together with overlapping ontological representations, demonstrates an obstruction to preparation independence. In fact, we establish a stronger structural result: the tensor product of any vertex of an -qubit Pauli polytope with any vertex of an -qubit Pauli polytope falls outside the composite -qubit polytope. These results obstruct a direct strategy for constructing composite ontological representations by independently sampling and tensoring local vertices. They therefore preclude a straightforward tensor-product approach to analyzing this simulation scheme, of the kind used in other classical simulation methods [19, 20, 39], without themselves establishing a lower bound on simulation time.
Outline
The remainder of the paper is organized as follows. § 3 reviews stabilizer theory and quantum computing with magic states. In § 4 we introduce the operational and ontological frameworks, antidistinguishability, and the preparation-independence argument. § 5 and § 6 develop our antidistinguishing measurements for stabilizer and magic-state preparations, respectively. In § 7 we apply these constructions to the Pauli ontological model and establishes the tensor-product obstruction for Pauli-polytope vertices. We conclude with a discussion of our results in § 8.
Quantum computing with magic states
Stabilizer theory
We begin with some preliminaries on stabilizer theory. A system of qubits is modeled by a Hilbert space . An -qubit Pauli operator is any operator of the form
where and each is a single-qubit Pauli matrix or the identity
For all , Pauli operators either commute or anticommute and are Hermitian if and only if . The -qubit Pauli group is the set of operators
with matrix multiplication as the group operation. A stabilizer group is an abelian subgroup of the Pauli group not containing . Every element of is therefore Hermitian and squares to the identity. Such a group has independent generators,
and has order . Note that the generators may include an overall minus sign. The operator
is the projector onto the joint eigenspace of each . Measurement of a Pauli observable obtaining outcome is encoded by the projector , where . A stabilizer group is maximal when it has independent generators. In this case, the projector has rank one and is a stabilizer state.
The -qubit Clifford group is a finite subgroup of the -qubit unitary group and, up to phases, is the normalizer of the Pauli group. Equivalently, the Clifford group is generated by the single-qubit Hadamard and phase gates together with the two-qubit CNOT gate. All stabilizer states can be written as
where is a stabilizer state with stabilizer group and is a Clifford unitary. It is known that any stabilizer state can be written in the normal form
where is an affine subspace and is a quadratic form; see e.g., [40].
Any quantum computation initialized in a stabilizer state, then acted on by Clifford gates and measurements of Pauli observables, optionally with classical randomness and feedforward, can be efficiently simulated classically. This is the well-known Gottesman–Knill theorem [41].
Clifford hierarchy and magic state injection
One can promote the stabilizer fragment of quantum theory to a universal quantum computational model with access to non-stabilizer, or ‘magic’ resources. A common choice is , which amounts geometrically to a rotation about the -axis of the Bloch sphere. Particularly appealing about the gate is that it can be implemented in fault-tolerant architectures using state injection schemes [37].
In this setup, one can implement deterministically once supplied with a magic state
together with adaptive stabilizer operations. Thus, the primitives for universal quantum computation can be taken to be adaptive Clifford gates and Pauli measurements together with a supply of magic states. For drawing samples from a universal family of circuits, the primitives can be further refined to consist only of adaptive Pauli measurements and magic states [42]; see also [43, 44].
Other choices of universal gate sets admitting deterministic magic state injection using stabilizer operations are also possible, such as the controlled phase and controlled-controlled- gate [20]. These gates all belong to the third level of the Clifford hierarchy [38]. More generally, the th-level of the hierarchy is defined recursively by
with the first and second levels being the -qubit Pauli and Clifford groups, respectively. While the levels of the Clifford hierarchy do not generally form a group, the diagonal elements in each level do form a group. In particular, at each level we have the diagonal single-qubit unitary
so that , , and . Here is a root of unity. The diagonal Clifford hierarchy is naturally described by such roots of unity and phase polynomials [45].
The corresponding single-qubit resource states can be defined analogously to the state
For , the standard deterministic injection scheme for additionally requires a lower-level correction on one measurement branch. This correction can itself be implemented by state injection, with further lower-level corrections as required [38]. The -fold tensor product of is given by
where is the binary ring and is the Hamming weight of the bit string . For , the coefficients of this normalized state lie in the algebraic field . For every , the coefficients lie in this field after removing the common normalization factor. (See [46] as well as Appendix § 10 for further details.) This fact will prove useful in the developments below.
Antidistinguishability
Operational quantum theory
The primitives of an operational theory are preparation, transformation, and measurement procedures, together with their empirical outcome probabilities. In quantum theory, preparations are represented by density operators, which are positive operators of unit trace. Here we consider projective measurements with post-measurement states determined by the Lüders rule. In particular, our setup will allow for any quantum state as a valid preparation, but we will focus on a subset of projective measurements with the main example being sequences of Pauli measurements.
Consider a sequence of mutually commuting PVMs , with , that we denote collectively as . For an outcome sequence , define the joint projector
The probability of this sequence on a preparation is
Whenever this probability is positive, the corresponding post-measurement state is
We also allow classical randomization over the permitted procedures. Pure states are the extremal quantum preparations, while rank-one PVMs are the finest projective measurements; higher-rank PVMs can be obtained from them by coarse-graining.
Given a restricted set of measurement procedures , two preparations are single-shot distinguishable (SSD) if there exists a measurement and a subset of its outcome set such that
Thus the outcome determines with certainty which preparation was performed. With access to all PVMs, orthogonal quantum states are always SSD since there exists a PVM that perfectly distinguishes them.
Following Ref. [27], consider now a finite set of pure state preparations . Performing a measurement and obtaining outcome , we denote the set of post-measurement states by . The measurement is said to be a partitioning measurement for if the set of post-measurement states contains at least one SSD pair for every outcome .
Ontological models framework
Ontological models aim to reproduce empirical statistics using ontic, or physical, microstates and classical probability theory. For simplicity, we take the set of ontic states to be finite.1 A preparation of is represented by a probability distribution on . For two preparation distributions and , define their common subdistribution by
and their overlap by
The support of a distribution is defined as
Drawing on standard terminology, we say that an ontological model is -ontic if for every pair of distinct pure-state preparations and . Otherwise, it is -epistemic [7].
A projective measurement with outcome set is represented by a transition kernel
for every . This kernel specifies the joint probability of obtaining outcome and transitioning to , conditional on the initial ontic state . The measurement response functions are obtained by marginalizing over the final ontic state:
and the model reproduces the operational probabilities when
Whenever this probability is positive, the conditional post-measurement distribution is
This distribution must reproduce the subsequent measurement statistics of the corresponding Lüders post-measurement state.
Antidistinguishing measurements
For preparations that are SSD, the measurement procedure that achieves this separation is called a distinguishing measurement. We will now consider antidistinguishing measurements (ADMs), which are measurements whose outcomes certify that some preparations were definitely not used in that run of the experiment, but typically do not confirm which preparation was actually used.
Consider a finite preparation family with measurement set . Following [12], we say that a projective measurement is a weakly antidistinguishing measurement (WADM) for this family if there exists a map such that
Equivalently, every measurement outcome is excluded by at least one member of the preparation family. We say is a strongly antidistinguishing measurement (SADM) if it is a WADM and, for every , there exists an outcome such that
Since every SADM is also a WADM, we establish our results for the weak case unless stated otherwise. We will often use ADM simply as an abbreviation broadly referring to antidistinguishing measurement without invoking the specific qualifiers above.
Theorem 4.1. If a finite preparation family admits a WADM, then every ontological model reproducing its zero probabilities satisfies
Proof. Suppose that belongs to the support of every . For each outcome , the WADM condition gives
Every summand is nonnegative. Since , it follows that . This holds for every , contradicting .
Let be two preparations. For , define their complete product family by
The ontological model satisfies preparation independence for this family if its composite ontic space is and the preparation is represented by a product distribution
Corollary 4.2 (PBR argument [9]). Suppose the complete -copy product family generated by admits a WADM. If an ontological model reproduces its zero probabilities and satisfies preparation independence, then
or equivalently, .
Proof. Suppose that . Preparation independence implies that, for every ,
Thus belongs to the common support of the entire product family, contradicting Theorem 4.1.
We remark that the PBR argument holds if and only if you regard preparation independence as fundamental. One could instead relinquish this principle by introducing additional ‘hidden’ correlations in the ontological representation of preparations, similar in spirit to how Bell’s theorem forces nonlocality in ontological models.
Proposition 4.3. If a preparation family admits a partitioning measurement whose conditional distinguishing measurements commute with its projectors, and the resulting adaptive measurement is allowed, then it admits a WADM.
Proof. Let be a partitioning measurement for . For each outcome , choose two preparations whose conditional post-measurement states are SSD. Here the indices may depend on . Conditional on , perform an allowed measurement that distinguishes these states. Writing for its outcome set, there exists a subset , with complement , such that
Let denote the resulting adaptive measurement, whose outcomes are pairs with . The joint probabilities satisfy
whenever the first factor is positive; otherwise the joint probability is zero. Consequently,
while
Writing for the projectors of and for those of , the joint effects are . By the commutation assumption, these are mutually orthogonal projectors summing to the identity. Thus is a PVM, not necessarily of rank one. Every outcome of therefore excludes at least one original preparation, so is a WADM.
Antidistinguishing measurements for stabilizer states
Simple examples of ADMs restricted to Pauli measurements and stabilizer state preparations go back to the original work of PBR [9]; see also [27]. Consider the nonorthogonal single-qubit stabilizer states
as well as the two-qubit state vectors
These rays form a PVM that can be implemented by the adaptive measurement sequence pictured in Figure 1. By direct calculation we have
Figure 1. The PVM in Eqns. (5a)-(5d) is implemented by an adaptive measurement tree: measure first, measure on the branch, and measure on the branch. Since each terminal outcome is orthogonal to its correspondingly labelled product preparation it is a SADM for these preparations.
Consequently, this is a SADM, which by Corollary 4.2 implies that a PBR proof exists in this case.
This example can be generalized to arbitrary nonorthogonal stabilizer states and . Our argument relies on the following standard result.
Lemma 5.1. Let and be distinct, non-orthogonal pure -qubit stabilizer states. There are a Clifford unitary , an integer , and a relabelling of tensor factors such that
Proof. First send to by a Clifford . From the stabilizer state normal form Eq. (1), we see that for the transformed to be non-orthogonal that the corresponding affine subspace is, in fact, a linear subspace containing the origin. We can perform row reduction on a basis of this linear subspace using CNOT and SWAP gates, which fix . Diagonal Clifford gates remove the remaining linear and quadratic phases, again while fixing up to phase. The second state is then . Requiring that the states be distinct gives .
The generalization then proceeds by choosing an odd number of active qubits in each block: take for odd and for even . The operators and , acting trivially on the remaining qubits, anticommute and define logical Pauli operators, with . In the corresponding logical-qubit subsystem, has logical state and has logical state ; their states on the remaining subsystem need not coincide. The common stabilizer tail does not enter the measurement. We then perform the logical two-qubit adaptive Pauli PVM of Figure 1 on the two preparation blocks. Its observables commute along each branch, so its terminal effects are mutually orthogonal projectors, which need not have rank one.
Proposition 5.2. An ontological model reproducing the predictions of stabilizer theory and satisfying preparation independence must represent distinct stabilizer states and by probability distributions and with disjoint support, i.e. .
The result holds since every terminal outcome of the logical Pauli PVM excludes one of the four product preparations. Orthogonal pairs are already distinguishable by a Pauli measurement. For a contextuality-based proof of this result, see Appendix § 11; similar connections between preparation independence and the contextuality of the stabilizer fragment were also explored in [33].
One straightforward consequence of Proposition 5.2 is that an ontological model reproducing the predictions of qubit stabilizer theory, but that does not represent non-orthogonal stabilizer states by disjoint probability distributions, must then violate preparation independence. An example of such a model is the closed non-contextual (CNC) phase space introduced in [21] (see also [47]), which provides an operator-based ontological model for qubit stabilizer quantum mechanics. These operators, however, are not closed under tensor product [48] so that preparation independence fails in this model. We prove a generalization of this result in § 7.3 for an operator-based ontological model of universal QCM.
Antidistinguishing measurements for magic states
The input resource state for QCM is often taken to be a tensor product of magic states. In this section we construct WADMs for non-stabilizer input states. For convenience, we will often drop normalization factors, as they do not affect the zero-probability condition.
Partitioning measurement for third-level states
Here we establish WADMs for tensor products of magic states by constructing a partitioning measurement. Let , where is orthogonal to . Define now
or more explicitly
Consider now the parity measurement of the two-qubit Pauli yielding the post-measurement states represented, up to phase and normalization, by
where and correspond to the even and odd parity subspaces, respectively. These are, in fact, stabilizer states satisfying
Thus, conditional on the outcome , measure ; conditional on , measure . Each conditional measurement distinguishes the two possible post-measurement states. The Pauli is therefore a partitioning measurement for this set of states and the conditional measurements and extend this to a WADM. This is precisely the adaptive measurement sequence in Figure 1, up to single-qubit Clifford unitaries.
Proposition 6.1. For every , the preparation family
admits a rank-one WADM implemented by adaptive Pauli measurements.
Proof. Partition the qubits into disjoint pairs. On each pair , measure , followed by on the branch and on the branch. If is odd, measure on the remaining qubit. The preceding two-qubit calculation shows that the second outcome on each pair is deterministically . Thus, every complete outcome string excludes preparations with the opposite parity on any pair, establishing the WADM property. We see that along each branch, the protocol measures independent commuting Pauli observables, whose joint eigenspaces have rank one. Distinct branches give orthogonal projectors, since their first differing outcomes belong to orthogonal eigenspaces of the same observable. Thus these projectors form a rank-one PVM.
Although and are orthogonal, they are not SSD by a single Pauli measurement, and so their ontological representations could, in principle, overlap in this restricted setting. The WADM constructed above, together with Corollary 4.2, however, rules this out under preparation independence.
For later developments, the same protocol also gives a conclusion assuming independence only between two blocks. We write the block states explicitly as and .
Corollary 6.2 (Block preparation independence). For , let , , and represent , , and , respectively. Suppose an ontological model reproduces the adaptive Pauli protocol above and represents the composite preparations
by and , respectively. Then
or equivalently, . Preparation independence is not assumed within either block.
Proof. Choose in the first block and in the second. For the two preparations, the selected qubits are in and , respectively. The two preparations can also differ on the unmeasured qubits, but these do not affect the selected-qubit probabilities. The two-qubit adaptive protocol described above therefore gives opposite deterministic second outcomes. Every terminal outcome excludes one of the two preparations, so the protocol is a WADM for this pair. Theorem 4.1 gives
The intersection equals
Since is normalized, its support is nonempty, and the result follows.
A hierarchy of antidistinguishing measurements
We now generalize the previous construction, based on the parity measurements, to construct WADMs for additional families of preparations arising from higher levels of the Clifford hierarchy. Define the single-qubit states
where and are as in Section 3. Recall that . The two states are nonorthogonal for every . To each -bit string , we associate the preparation
where is evaluated over the integers so that the exponent of is evaluated modulo four, not modulo two. Let be a stabilizer state. Using the normal form in Eq. (1), we have the overlap
We will be interested in when these overlaps are precisely zero, since this corresponds to the outcome of a stabilizer PVM having zero probability.
To this end, it will be useful to interpret this overlap through the polynomial in a complex variable with coefficients in
which is a field [46]; see also Appendix § 10. This polynomial has degree at most . At the same time, the minimal polynomial of over is given by
which has degree . These algebraic developments are important for making the following observation.
Observation 6.3. If , then a stabilizer overlap in (12) vanishes if and only if is the zero polynomial. Equivalently, every Hamming-weight coefficient vanishes separately. In particular, the first qubit number at which a zero can use the new algebraic relation is .
The threshold establishes the minimal number of qubits at which a nonzero overlap polynomial can vanish at . Below the threshold, zero overlaps can still occur through cancellation within each Hamming-weight coefficient. Indeed, at the threshold , we have the cat state
with stabilizer group
This state gives an algebraic zero
The threshold alone does not establish the minimum number of qubits needed for a WADM. At the threshold, however, we have the following result for every .
Theorem 6.4. For every , the complete product family generated by the nonorthogonal single-qubit states in (11) admits a rank-one stabilizer WADM on
independently prepared copies.
The key observation is that a parity measurement acting on yields the even and odd parity post-measurement states represented, up to phase and normalization, by
The odd case yields a stabilizer state. In the even case, since
we recognize the post-measurement state as an encoded single qubit with phase level . Here the encoding is and . Note that the exponent is an integer sum, so it may equal two. For the recursive construction, we use the inputs 00 and 01, which give the encoded states and , respectively. Our proof will use this recursive property to construct a WADM.
To see how this works, let us work out the cases , the first two nontrivial instances. For we use qubits. Let label the product preparation . Performing first the parity measurement we obtain
Notice that both post-measurement states are stabilizer states in this case. Measure next the Pauli , regardless of outcome. Equivalently, we perform the stabilizer PVM with rays
It is straightforward to check that each vector is an eigenstate of both and . The labeling is chosen such that the preparation is excluded by the PVM element projecting onto .
The higher-level case of will build on the lower-level measurement scheme. Now we use qubits. Recall that and . The bit string corresponds to the product preparation
Pair qubits and and first measure and . Introduce the even and odd code bases
together with the logical eigenstates, for ,
After the parity measurement on either pair, the projected two-qubit states are
For inputs , the even pair forms an encoded version of or , respectively, one level lower in the hierarchy. On an odd pair we have that the string corresponds to the stabilizer state ; similarly, to , and both and correspond to .
The initial two parity measurements produce the syndrome , where . Whenever we obtain an odd parity syndrome outcome there is a qubit pair in a stabilizer state on which a logical measurement excludes input for one outcome and input for the other. The syndrome is the recursive branch since, as mentioned above, the selected inputs on each even pair give encoded single-qubit third-level states. Our stabilizer PVM will use the four stabilizer rays
These are exactly the encoded versions of the measurement vectors in Eq. (18). All four syndrome subspaces are refined to rank-one elements by the following independent, conditional Pauli measurements:
| syndrome | conditional Pauli generators |
Table 18.
The last three rows produce the remaining orthogonal vectors
Altogether, the four sets in (17) and (19) give the sixteen-ray stabilizer PVM. In Table 1 we identify a bijection between preparations and the corresponding impossible outcome. In the non-even rows, the first ket refers to qubits (1,2) and the second to qubits (3,4). Every one of the sixteen preparation words occurs exactly once.
| Syndrome | PVM ray | Preparation |
| 0000 | ||
| 0001 | ||
| 0100 | ||
| 0011 | ||
| 1001 | ||
| 1101 | ||
| 0010 | ||
| 1110 | ||
| 0101 | ||
| 0110 | ||
| 1000 | ||
| 1010 | ||
| 0111 | ||
| 1100 | ||
| 1011 | ||
| 1111 |
Table 1. Each product preparation , labeled by , is orthogonal to its assigned stabilizer PVM ray.
Proof of Theorem 6.4. We recursively construct a measurement . For , use the two-qubit ADM defined above. For , pair the qubits and proceed as follows.
Measure on every pair, obtaining a syndrome .
If contains an , choose the first odd pair. Measure logical on this pair and logical on every remaining pair.
If is all even, apply to the encoded qubits, using and .
To verify the WADM property, consider a complete outcome. In step 2, the inputs 01 and 10 on the selected odd pair give opposite logical eigenstates. Either logical- outcome therefore excludes one of these inputs, independently of the inputs and subsequent outcomes on the remaining pairs.
In step 3, the physical inputs 00 and 01 give the encoded states and . By induction, every recursive outcome excludes a logical preparation word. Replacing each logical 0 by 00 and each logical 1 by 01 gives an original preparation word excluded by the complete outcome.
All logical measurements are physical Pauli measurements: on each parity subspace, logical , , and can be represented by , , and , respectively. Each syndrome subspace is resolved into rank-one stabilizer projectors, directly in step 2 and recursively in step 3. Distinct syndrome subspaces are orthogonal, so the resulting measurement is a rank-one stabilizer PVM. Since every outcome excludes a preparation, it is a WADM.
Antidistinguishing measurements from complete graph states
We now introduce a somewhat different construction that gives a stabilizer SADM for every , with the preparation angle depending on . This construction is closer to the original argument due to [9]. In particular, we define
These states are nonorthogonal, since . For , write
We recall some facts about graph states; see e.g., [49]. For a graph with vertex set and edge set , the corresponding graph state is defined by
Every graph state is also a stabilizer state whose stabilizer group has the canonical generating set
where is the neighborhood of the vertex . The Pauli operator commutes with for and anticommutes with . Thus, we have the orthonormal stabilizer basis with rays
The complete graph has an edge between every pair of distinct vertices. Its corresponding graph state is
since and precisely entries of are equal to one. We let the corresponding orthonormal basis rays be written as .
Theorem 6.5. For every , the product preparations
admit a rank-one stabilizer ADM.
Proof. For preparation , let be the Hamming distance between and , and write , . Then
The signs follow the repeating pattern , and hence
Applying this identity and factoring the sum over bits gives
Since , this becomes
For , the argument lies in . On this interval, vanishes only at . Consequently,
Thus each measurement outcome excludes exactly one preparation, and each preparation has exactly one excluding outcome. In particular, the measurement is a SADM.
Our construction yields a PBR proof for every number of qubits. Although less general than the SADM proposed by PBR, it uses a measurement scheme built from Pauli measurements and graph states. The required angles enter through the preparations. Whether this simplification of the measurement protocol makes actual implementation simpler requires separate consideration.
Preparation independence in the Pauli ontological model
We now specialize our preceding results to the Pauli ontological model [35], which furnishes a classical simulation algorithm for universal QCM based on convex polytopes. (For preliminaries on convex polytopes, we refer the reader to [50].) Particularly relevant to any classical simulation algorithm is its scaling in , the number of qubits. In many approaches, including those based on quasiprobability distributions [19, 20] or stabilizer rank methods [39, 42, 51], tensor products provide a way to construct representations of larger systems from those of their constituent parts. Here we use our WADMs for magic states to show that such tensor-product constructions in the Pauli ontological model encounter obstructions arising from the PBR argument.
The Pauli polytopes
Let denote the set of pure -qubit stabilizer states. The -qubit Pauli polytope, also called the polytope, is defined as the intersection of halfspace inequalities
This is a bounded polytope [35], and hence the convex hull of its finitely many vertices [50]. We label the extreme points of by .
Every quantum state belongs to and therefore admits a decomposition
The labels are interpreted as ontic states, and as a preparation distribution. Such decompositions, however, are generally not unique. A measurement of a Pauli observable is represented by a stochastic kernel satisfying
where is the projector associated with the outcome , and
The existence of these kernels follows from the behavior of under Pauli measurements; see [26, 35].
We are interested in whether independent preparations can be represented by independently sampled local ontic states. More technically, we study the corresponding operators combined by the tensor product. To this end, one compatibility result has already been established. For any , any stabilizer state , and any -qubit Clifford unitary , the operator
is a vertex of [48]. This construction adds only stabilizer ancillas and Clifford processing, and therefore introduces no additional computational resource.
More relevant for quantum computation are tensor products of non-stabilizer resource states, such as those supplied by magic-state distillation protocols [37]. For general preparations, consider decompositions
Their tensor product satisfies
The coefficients form a product probability distribution, as required by preparation independence. The remaining question is whether the tensored operators are valid elements of .
Were we to have , then this construction yields an ontological model for universal QCM satisfying preparation independence. Indeed, if , then every stabilizer projective measurement has a normalized, non-negative response function
Moreover, if belongs to , it is in fact a vertex of .2 Consequently, closure under tensor products of local vertices would identify each pair with a global ontic state and provide an operator realization of preparation independence.
Our results up until this point suggest that preparation independence should fail for the magic states considered thus far, provided that their preparation distributions have overlapping support. In the next sections, we show that the geometry of the Pauli polytopes allows us to choose such distributions for distinct magic states.
Convex geometry of Pauli polytopes
The vertices that can appear in a decomposition of are determined by its vanishing stabilizer probabilities. Indeed, if a stabilizer state satisfies , then
Since every term is nonnegative, this implies for all . These feasible vertices are elements of the carrier face of introduced below; see also [53].
Recall that is a face of if it is of the form
where is any subset of stabilizer states. Note that can be the empty set. Fix some and let be the set of stabilizer rays with zero expectation on . The carrier face of is then the inclusion minimal face of containing . It is given by
In particular, we have that is in the relative interior of [50]. Geometrically, this means that there exists a ball of dimension centered at with suitable radius contained in .
The vertices of are therefore precisely those vertices of satisfying the above orthogonality conditions [53]. We define the vertex support of by
Every vertex decomposition of satisfies
Conversely, every label in can occur with positive probability in some decomposition of .
Lemma 7.1. Let be a nonempty face of and . For every , there exists a vertex decomposition of with .
Proof. Since , for sufficiently small the point
belongs to . Decomposing into vertices of and substituting into
gives the required decomposition.
The following proposition identifies exactly when two operators admit decompositions with a common ontic state.
Proposition 7.2. For , the following are equivalent:
There exist vertex decompositions such that
Their carrier faces satisfy
In particular, if , then any vertex of this common face can occur with positive coefficient in decompositions of both and .
Proof. If belongs to the support of both decompositions, then . Conversely, a nonempty intersection is a face of and therefore contains a vertex of . This is a vertex of both carrier faces. Applying Lemma 7.1 separately to and one can construct preparation distributions such that and .
We can extend this result so that every vertex of appears simultaneously with strictly positive weight in a single decomposition.
Corollary 7.3. Let be a face of a polytope. Every admits a decomposition
In particular, states with the same carrier face admit vertex decompositions with the same support.
Proof. Let be the uniform average of the vertices of . Since , for sufficiently small we have
Expressing as a convex combination of the vertices of and substituting into gives a strictly positive coefficient for every vertex.
Thus, to establish the existence of overlapping preparation distributions, it suffices to show that the two states have the same carrier face. Notice, however, that this is a statement about which admissible decompositions exist. Not every pair of decompositions need overlap, even if the points share the same carrier face. An exception is when the carrier face is a simplex since the extremal points are then affinely independent.
Ontic supports for magic states
We now analyze the carrier faces of magic states, with a particular emphasis on -state preparations. A similar analysis for higher-level phases is straightforward. Introduce the notation
Here denotes the projector onto , rather than the complementary projector . Our goal is to show that and have the same carrier face. They will then admit vertex decompositions with common strictly positive support.
For a stabilizer ray , the Born probability
vanishes precisely when . Recall the overlap in Eq. (12) and specialize to and . Since , separate the even and odd Hamming weights of the overlap polynomial according to
Because and are linearly independent over , a zero overlap requires . Physically, the amplitudes cancel separately in the even and odd sectors. Observe that applying the unitary changes only the relative sign of these sectors, so it cannot undo either cancellation.
Proposition 7.4. For every , the states and have the same carrier face , and hence the same vertex support.
Proof. The operator multiplies the amplitude at by . The overlap with is therefore proportional to . By linear independence, this vanishes if and only if . Thus the two states have exactly the same orthogonal stabilizer projectors and the same carrier face.
The same argument permits a continuous change of relative phase between the parity sectors. Let
Proposition 7.5. For every and , . If , the transformed state has carrier face exactly . In particular, this holds for .
Proof. The transformed overlap is proportional to
Every original zero is preserved since . For , we have exact equality of the zero sets.
At exceptional angles, new stabilizer zeros can appear and the state can move to a proper subface. A second remark concerns symmetries. The Pauli polytopes are dual to the stabilizer polytopes and therefore have the extended Clifford group as their symmetry group [36]. The unitary above is therefore not a symmetry of , except in special cases. Instead, it is a symmetry of a convex set within .
Tensor obstruction for magic state supports
In this section we show that tensoring operator decompositions of -states need not give a valid decomposition in the composite Pauli polytope. The argument combines the carrier face results above with the two-block -state protocol of § 6.1. The underlying obstruction is that independent local sampling can produce a product operator that assigns a negative probability to a stabilizer measurement outcome.
Since and have the same carrier face, they admit decompositions with strictly positive weights on overlapping vertices (Corollary 7.3). Tensoring these decompositions with a fixed decomposition of preserves this overlap. However, the protocol of § 6.1, together with Corollary 6.2, perfectly distinguishes these two composite preparations using adaptive Pauli measurements. Consequently, they cannot share an ontic state with valid response functions. At least one of the product operators in the common support must therefore lie outside the composite Pauli polytope.
Proposition 7.6. For every , there exist vertices and such that
Proof. Choose decompositions of positive on every vertex of , and of both and positive on every vertex of . The composite preparations
then have strictly positive decompositions over the product ontic space . Suppose every in this product set belongs to . Let be the stabilizer measurement from Corollary 6.2. For each outcome , at least one of and is zero. Expanding that preparation gives a strictly positive sum of nonnegative terms . Every such term must vanish. For any fixed pair of vertices, however,
a contradiction.
This argument shows only that some product operator violates a stabilizer inequality. One could imagine, however, that a carefully chosen decomposition could avoid the problematic product operator(s), thereby salvaging the construction. In the next section we show that this is not the case.
A general tensor obstruction for qubits
We now establish a stronger structural result about Pauli polytopes: every tensor product of two qubit Pauli-polytope vertices lies outside the composite polytope.
For and , every product stabilizer state satisfies
Thus, any violation must be witnessed by an entangled stabilizer state. For vertices, we construct such a witness by superposing two carefully chosen product stabilizer states. Each product state has a local factor with zero expectation on the corresponding vertex.
Lemma 7.7. Let , with . There exist two orthogonal stabilizer states , , agreeing on independent stabilizer generators and differing in the sign of one remaining generator, such that
Their phases can be chosen so that they are the encoded computational basis of a rank-two stabilizer code.
Proof. Let denote the set of tight stabilizer rays, namely those satisfying . Since is a vertex, the identity together with the projectors formed from span the real vector space of Hermitian operators. Otherwise, there would be a nonzero traceless Hermitian direction preserving all tight equalities, along which both sufficiently small positive and negative perturbations of remain in , contradicting extremality; see e.g., [54].
First, we need to show that not every satisfies . We proceed by contradiction. Suppose instead that every tight stabilizer ray belongs to . Since , is not the zero operator and is a proper subspace. This means we can choose unit vectors and , and define the Hermitian operator
Observe that and for every tight stabilizer ray , since . In particular, we have for all so that all tight equalities are preserved along . Since all remaining stabilizer inequalities are strict, there exists a sufficiently small such that . This contradicts extremality. Hence some tight stabilizer ray satisfies .
Recall that any stabilizer state is of the form , for some Clifford unitary . Complete to an orthonormal stabilizer basis by applying to the computational basis. Since is not in the kernel of and because is a basis, there exists some such that . It is known that two stabilizer rays related by the same unitary to the computational basis can rearrange their stabilizer generators so that they differ in the sign of just a single generator. Removing that generator yields a rank-two stabilizer code.
Theorem 7.8. For all and all vertices and ,
More precisely, there is an entangled rank-one stabilizer projector with .
Proof. Apply Lemma 7.7 to and . Choose encoded stabilizer pairs satisfying
Put and consider the product states
Their expectations vanish:
Their off-diagonal matrix element, however, is
Let and denote the logical Pauli operators distinguishing the two states in each local pair. The vectors share the local code generators and the additional generator . They therefore span a rank-two stabilizer code. With the phases fixed by the local Clifford encodings, its complementary logical Pauli bases consist of
These are rank-one stabilizer states, each entangled across the partition. Direct calculation gives
Since , at least one of these expectations is strictly negative. In fact, the violating projector can be chosen so that
Thus violates a defining stabilizer inequality of .
Consequently, independently sampling local vertex decompositions and returning the operator never produces a valid composite ontic operator. In short: preparation independence fails for the Pauli ontological model.
Conclusion
In this paper we initiated the development of PBR proofs for non-stabilizer preparation families using Pauli measurements. For the single-qubit preparation families considered at levels of the Clifford hierarchy, we showed that stabilizer-restricted PBR proofs exist using independently prepared systems. Beyond these Clifford-hierarchy families, we also constructed such measurement schemes for every , with the preparation states depending on . Although these constructions do not necessarily provide new conceptual insights into the PBR theorem, they open an avenue for studying particularly simple and elegant proofs, similar in spirit to the study of Kochen–Specker proofs [55, 56]. Particularly interesting is the role of algebraic number theory in the geometry of stabilizer-restricted antidistinguishability, which our work has only begun to explore. Related connections between number theory and quantum-state geometry have been developed, for instance, in the study of SIC measurements [57].
We also demonstrated a general obstruction to preparation independence in ontological representations of qubit stabilizer theory. Our results imply that any such model satisfying preparation independence must be -ontic on pure stabilizer states, suggesting the stabilizer states themselves as a natural candidate ontic state space. Indeed, these states also serve as the underlying state space in quasiprobability representations of qubit stabilizer theory [20]. This contrasts with the odd-prime-dimensional qudit case, where stabilizer states have nonnegative Gross Wigner representations and the phase-point operators are closed under tensor products. Several distinctions between the even- and odd-dimensional cases have been related to topological obstructions [34]. Whether related obstructions also account for the difference in tensor-product structure appears plausible (see Appendix § 11), but remains an interesting question for future work.
Our results also connect the operational constraints imposed by antidistinguishability to the geometry of Pauli polytopes. In this representation, the obstruction to preparation independence appears concretely as a failure of closure under tensor products: the tensor product of any two local vertices lies outside the corresponding composite-system polytope. This restricts how these polytopes can represent independently prepared systems. From a categorical perspective, it appears to obstruct a monoidal representation in which parallel composition is implemented by the ordinary operator tensor product. While a full categorical treatment of polyhedral classical simulation schemes [58] remains open, some steps in this direction were taken in [59].
This question also bears on the computational complexity of polytope-based classical simulation. Zurel et al. [60] showed that the simulation requires only polynomially many bits to describe its instantaneous state, leaving the presumed computational hardness in the initial sampling or subsequent measurement updates. An efficiently implementable tensor-product rule would make initialization of fixed single-qubit product inputs straightforward: one could sample the local distributions independently and compose the resulting ontic states. Our result rules out this construction using operator tensor products of local vertices. It does not establish the hardness of initial sampling, but it does remove a natural reason to expect initialization to be easy. The difficulty of classical simulation may therefore arise before the first measurement, in representing completely unentangled inputs within an ontological state space not admitting a product structure.
Acknowledgments
The author thanks P. Mitosek, R. Raussendorf, and A. T. Yücel for useful discussions. The author acknowledges support from the Niedersächsisches Ministerium für Wissenschaft und Kultur and the Alexander von Humboldt Foundation. The author acknowledges the use of ChatGPT in literature review, manuscript revision, and the development of mathematical arguments. The author has verified the final results and takes full responsibility for the manuscript.
Algebra background
Here we recall the facts about field extensions and cyclotomic fields used in the main text. For a detailed treatment, see, e.g., [46].
Field extensions
Let be a field and let be algebraic over , meaning that it is a root of a nonzero polynomial in . The minimal polynomial is the unique monic polynomial of least degree satisfying . It is irreducible over , and
In particular, no nonzero polynomial of degree less than can vanish at .
The field is the smallest field containing and . Its degree over is its dimension as an -vector space, and
For a tower of finite extensions , the degrees satisfy
Cyclotomic fields
A primitive th root of unity is . Its minimal polynomial over is the cyclotomic polynomial
This polynomial is irreducible over and has degree , where is Euler’s totient function. Consequently,
In the main text we use . For , we have , so . The tower law therefore gives
Since , the polynomial vanishes at and has precisely this degree. It is therefore the minimal polynomial of over . Thus, for ,
In particular, if , then only when is the zero polynomial. This is the algebraic constraint used in the stabilizer-overlap argument.
Contextuality-based PBR theorem for stabilizer states
We now give a contextuality-based proof using the notation and conventions of the main body together with the results of [27], which connect contextuality to partitioning measurements. For a preparation family , let be the set of Hermitian Pauli observables whose measurement has a deterministic outcome on at least one . Denote its closure under products of commuting observables by . The relevant Kochen–Specker relations are
These relations express the algebraic constraints on compatible measurement outcomes.
In the ontological model, preparations are represented by probability distributions . We assume that the response functions are noncontextual under fine-graining: if refines , with
then
In particular, the response to a coarse-grained outcome is independent of the chosen refinement.
Suppose now that there exists some in the joint support of the preparations, i.e. . For every , some preparation has a deterministic outcome . Nonnegativity of the ontological representation therefore gives
If two preparations impose different values on the same observable, this already excludes a common . Now let be commuting observables whose responses at are deterministic. Their joint measurement refines both and , so its response is concentrated on . The same joint measurement refines , with product outcome . Consequently,
Iterating this argument extends the deterministic assignment to , where it satisfies
If admits a proof of state-independent contextuality, no such assignment exists. Thus we conclude
Similar notions have been developed in [27].
Consider now two distinct, nonorthogonal pure stabilizer preparations , with stabilizer groups . There exist anticommuting and . Otherwise, maximality would imply that the two groups have the same unsigned observables, making the states either identical or orthogonal. Define the preparations
Since these are stabilizer states, the set of observables and its closure are nonempty.
Proposition B.1. The closure contains a Mermin square. Consequently, every ontological model reproducing the allowed measurements and state updates satisfies
Proof. Put , so that is a Hermitian Pauli observable. Consider the array
This is precisely the structure of the Peres-Mermin square [61]. The first eight observables belong to , each having deterministic value on some preparation. The final observable belongs to since
Each row and column consists of commuting observables. The row products are , while the column products are , , , precluding a consistent value assignment. By the construction of Karanjai et al. [27 Theorem 2], is a partitioning measurement, thus excluding common ontic support for the states in .
Corollary B.2. An ontological model reproducing qubit stabilizer theory and satisfying preparation independence must represent distinct pure stabilizer preparations by distributions satisfying
Proof. Orthogonal stabilizer preparations are SSD and therefore have disjoint supports. For a distinct nonorthogonal pair, the result follows from Proposition B.1.
Thus a model with overlapping distributions for distinct pure qubit stabilizer states must violate preparation independence. Note that a similar result for qudit stabilizer theory with odd local dimension does not hold. In that case the Wigner representation yields a noncontextual model that is also closed under tensor product, thus satisfying preparation independence. As a concluding remark, we note that the Mermin-Peres square paradox [61] can be understood topologically [62].
References
- [1]J. S. Bell, “On the Einstein Podolsky Rosen paradox,” Physics Physique Fizika, vol. 1, no. 3, p. 195, 1964. https://doi.org/10.1103/physicsphysiquefizika.1.195.
- [2]S. Kochen and E. P. Specker, “The problem of hidden variables in quantum mechanics,” in Ernst Specker Selecta, pp. 235–263, Springer, 2011. https://doi.org/10.1007/978-3-0348-9259-9_21.
- [3]J. S. Bell, “On the problem of hidden variables in quantum mechanics,” Reviews of Modern physics, vol. 38, no. 3, p. 447, 1966. https://doi.org/10.1103/revmodphys.38.447.
- [4]R. W. Spekkens, “Contextuality for preparations, transformations, and unsharp measurements,” Physical Review A—Atomic, Molecular, and Optical Physics, vol. 71, no. 5, p. 052108, 2005. https://doi.org/10.1103/physreva.71.052108.
- [5]E. Wigner, “On the quantum correction for thermodynamic equilibrium,” Physical review, vol. 40, no. 5, p. 749, 1932. https://doi.org/10.1103/physrev.40.749.
- [6]C. Ferrie and J. Emerson, “Frame representations of quantum mechanics and the necessity of negativity in quasi-probability representations,” Journal of Physics A: Mathematical and Theoretical, vol. 41, no. 35, p. 352001, 2008. https://doi.org/10.1088/1751-8113/41/35/352001.
- [7]N. Harrigan and R. W. Spekkens, “Einstein, incompleteness, and the epistemic view of quantum states,” Foundations of Physics, vol. 40, no. 2, pp. 125–157, 2010. https://doi.org/10.1007/s10701-009-9347-0.
- [8]L. Hardy, “Quantum theory from five reasonable axioms,” arXiv preprint quant-ph/0101012, 2001. https://arxiv.org/abs/quant-ph/0101012.
- [9]M. F. Pusey, J. Barrett, and T. Rudolph, “On the reality of the quantum state,” Nature Physics, vol. 8, pp. 475–478, 2012. https://doi.org/10.1038/nphys2309.
- [10]C. M. Caves, C. A. Fuchs, and R. Schack, “Conditions for compatibility of quantum-state assignments,” Physical Review A, vol. 66, no. 6, p. 062111, 2002. https://doi.org/10.1103/physreva.66.062111.
- [11]M. S. Leifer, “Is the quantum state real? an extended review of ψ-ontology theorems,” arXiv preprint arXiv:1409.1570, 2014. https://arxiv.org/abs/1409.1570.
- [12]M. Srikumar, S. D. Bartlett, and A. Karanjai, “How contextuality and antidistinguishability are related,” Physical Review Letters, vol. 136, p. 080203, 2026. https://doi.org/10.1103/tlh1-xwks.
- [13]R. Raussendorf and H. J. Briegel, “A one-way quantum computer,” Phys. Rev. Lett., vol. 86, pp. 5188–5191, May 2001. https://doi.org/10.1103/PhysRevLett.86.5188.
- [14]J. Anders and D. E. Browne, “Computational power of correlations,” Physical Review Letters, vol. 102, no. 5, p. 050502, 2009. https://doi.org/10.1103/physrevlett.102.050502.
- [15]M. J. Hoban, E. T. Campbell, K. Loukopoulos, and D. E. Browne, “Non-adaptive measurement-based quantum computation and multi-party bell inequalities,” New Journal of Physics, vol. 13, no. 2, p. 023014, 2011. https://doi.org/10.1088/1367-2630/13/2/023014.
- [16]R. Raussendorf, “Contextuality in measurement-based quantum computation,” Phys. Rev. A, vol. 88, p. 022322, Aug 2013. https://doi.org/10.1103/PhysRevA.88.022322.
- [17]M. Frembs, S. Roberts, E. T. Campbell, and S. D. Bartlett, “Hierarchies of resources for measurement-based quantum computation,” New Journal of Physics, vol. 25, no. 1, p. 013002, 2023. https://doi.org/10.1088/1367-2630/acaee2.
- [18]V. Veitch, C. Ferrie, D. Gross, and J. Emerson, “Negative quasi-probability as a resource for quantum computation,” New Journal of Physics, vol. 14, no. 11, p. 113011, 2012. https://doi.org/10.1088/1367-2630/14/11/113011.
- [19]H. Pashayan, J. J. Wallman, and S. D. Bartlett, “Estimating outcome probabilities of quantum circuits using quasiprobabilities,” Physical review letters, vol. 115, no. 7, p. 070501, 2015. https://doi.org/10.1103/physrevlett.115.070501.
- [20]M. Howard and E. Campbell, “Application of a resource theory for magic states to fault-tolerant quantum computing,” Physical review letters, vol. 118, no. 9, p. 090501, 2017. https://doi.org/10.1103/physrevlett.118.090501.
- [21]R. Raussendorf, J. Bermejo-Vega, E. Tyhurst, C. Okay, and M. Zurel, “Phase-space-simulation method for quantum computation with magic states on qubits,” Physical Review A, vol. 101, no. 1, p. 012350, 2020. https://doi.org/10.1103/physreva.101.012350.
- [22]M. Howard, J. Wallman, V. Veitch, and J. Emerson, “Contextuality supplies the ‘magic’ for quantum computation,” Nature, vol. 510, no. 7505, pp. 351–355, 2014. https://doi.org/10.1038/nature13460.
- [23]N. Delfosse, C. Okay, J. Bermejo-Vega, D. E. Browne, and R. Raussendorf, “Equivalence between contextuality and negativity of the Wigner function for qudits,” New Journal of Physics, vol. 19, no. 12, p. 123024, 2017. https://doi.org/10.1088/1367-2630/aa8fe3.
- [24]D. Schmid, H. Du, J. H. Selby, and M. F. Pusey, “Uniqueness of noncontextual models for stabilizer subtheories,” Physical Review Letters, vol. 129, no. 12, p. 120403, 2022. https://doi.org/10.1103/physrevlett.129.120403.
- [25]R. Raussendorf, D. E. Browne, N. Delfosse, C. Okay, and J. Bermejo-Vega, “Contextuality and Wigner-function negativity in qubit quantum computation,” Physical Review A, vol. 95, no. 5, p. 052334, 2017. https://doi.org/10.1103/physreva.95.052334.
- [26]C. Okay, A. T. Yucel, and S. Ipek, “Classical simulation of universal measurement-based quantum computation using multipartite Bell scenarios,” arXiv preprint arXiv:2410.23734, 2024. https://arxiv.org/abs/2410.23734.
- [27]A. Karanjai, J. J. Wallman, and S. D. Bartlett, “Contextuality bounds the efficiency of classical simulation of quantum processes,” arXiv preprint arXiv:1802.07744, 2018. https://arxiv.org/abs/1802.07744.
- [28]A. Montina, “Exponential complexity and ontological theories of quantum mechanics,” Physical Review A—Atomic, Molecular, and Optical Physics, vol. 77, no. 2, p. 022104, 2008. https://doi.org/10.1103/physreva.77.022104.
- [29]M. Kleinmann, O. Gühne, J. R. Portillo, J.-Å. Larsson, and A. Cabello, “Memory cost of quantum contextuality,” New Journal of Physics, vol. 13, no. 11, p. 113011, 2011. https://doi.org/10.1088/1367-2630/13/11/113011.
- [30]D. Gross, “Hudson’s theorem for finite-dimensional quantum systems,” Journal of mathematical physics, vol. 47, no. 12, 2006. https://doi.org/10.1063/1.2393152.
- [31]N. Delfosse, P. Allard Guerin, J. Bian, and R. Raussendorf, “Wigner function negativity and contextuality in quantum computation on rebits,” Physical Review X, vol. 5, no. 2, p. 021003, 2015. https://doi.org/10.1103/physrevx.5.021003.
- [32]J. Bermejo-Vega, N. Delfosse, D. E. Browne, C. Okay, and R. Raussendorf, “Contextuality as a resource for models of quantum computation with qubits,” Physical review letters, vol. 119, no. 12, p. 120505, 2017. https://doi.org/10.1103/physrevlett.119.120505.
- [33]P. Lillystone and J. Emerson, “A contextual ψ-epistemic model of the n-qubit stabilizer formalism,” arXiv preprint arXiv:1904.04268, 2019. https://arxiv.org/abs/1904.04268.
- [34]R. Raussendorf, C. Okay, M. Zurel, and P. Feldmann, “The role of cohomology in quantum computation with magic states,” Quantum, vol. 7, p. 979, 2023. https://doi.org/10.22331/q-2023-04-13-979.
- [35]M. Zurel, C. Okay, and R. Raussendorf, “Hidden variable model for universal quantum computation with magic states on qubits,” Physical Review Letters, vol. 125, no. 26, p. 260404, 2020. https://doi.org/10.1103/physrevlett.125.260404.
- [36]M. Heinrich and D. Gross, “Robustness of magic and symmetries of the stabiliser polytope,” Quantum, vol. 3, p. 132, 2019. https://doi.org/10.22331/q-2019-04-08-132.
- [37]S. Bravyi and A. Kitaev, “Universal quantum computation with ideal Clifford gates and noisy ancillas,” Physical Review A, vol. 71, no. 2, p. 022316, 2005. https://doi.org/10.1103/physreva.71.022316.
- [38]D. Gottesman and I. L. Chuang, “Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations,” Nature, vol. 402, no. 6760, pp. 390–393, 1999. https://doi.org/10.1038/46503.
- [39]S. Bravyi and D. Gosset, “Improved classical simulation of quantum circuits dominated by Clifford gates,” Physical review letters, vol. 116, no. 25, p. 250501, 2016. https://doi.org/10.1103/physrevlett.116.250501.
- [40]M. Van den Nest, “Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond,” Quantum Information and Computation, vol. 10, no. 3&4, pp. 258–271, 2010. https://doi.org/10.26421/QIC10.3–4–6.
- [41]D. Gottesman, “The Heisenberg representation of quantum computers,” in Group22: Proceedings of the XXIII International Colloquium on Group Theoretical Methods in Physics (S. P. Corney, R. Delbourgo, and P. D. Jarvis, eds.), (Cambridge, MA), pp. 32–43, International Press, 1999. https://arxiv.org/abs/quant-ph/9807006.
- [42]S. Bravyi, G. Smith, and J. A. Smolin, “Trading classical and quantum computational resources,” Physical Review X, vol. 6, no. 2, p. 021043, 2016. https://doi.org/10.1103/physrevx.6.021043.
- [43]M. Yoganathan, R. Jozsa, and S. Strelchuk, “Quantum advantage of unitary Clifford circuits with magic state inputs,” Proceedings of the Royal Society A, vol. 475, no. 2225, p. 20180427, 2019. https://doi.org/10.1098/rspa.2018.0427.
- [44]F. C. R. Peres, S. Ipek, D. Lovsted, J. Nevin, and A. Broadbent, “Normal-form characterization of adaptivity and entanglement in Pauli-based computation,” arXiv preprint arXiv:2610.30315, 2026. https://arxiv.org/abs/2610.30315.
- [45]S. X. Cui, D. Gottesman, and A. Krishna, “Diagonal gates in the Clifford hierarchy,” Physical Review A, vol. 95, no. 1, p. 012329, 2017. https://doi.org/10.1103/PhysRevA.95.012329.
- [46]I. N. Herstein, Topics in algebra. John Wiley & Sons, 1991.
- [47]S. Ipek, A. T. Yucel, F. Shahi, C. Ozdemir, and C. Okay, “Phase-space tableau simulation for quantum computation,” Phys. Rev. A, vol. 113, p. 032409, Mar 2026. https://link.aps.org/doi/10.1103/11f2-nqht.DOI
- [48]C. Okay, M. Zurel, and R. Raussendorf, “On the extremal points of the Λ-polytopes and classical simulation of quantum computation with magic states,” arXiv preprint arXiv:2104.05822, 2021. https://arxiv.org/abs/2104.05822.
- [49]M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Van den Nest, and H.-J. Briegel, “Entanglement in graph states and its applications,” arXiv preprint quant-ph/0602096, 2006. https://arxiv.org/abs/quant-ph/0602096.
- [50]G. M. Ziegler, Lectures on polytopes, vol. 152. Springer Science & Business Media, 2012. https://doi.org/10.1007/978-1-4613-8431-1.
- [51]S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset, and M. Howard, “Simulation of quantum circuits by low-rank stabilizer decompositions,” Quantum, vol. 3, p. 181, 2019. https://doi.org/10.22331/q-2019-09-02-181.
- [52]M. Plávala, “General probabilistic theories: An introduction,” Physics Reports, 2023. https://doi.org/10.1016/j.physrep.2023.09.001.
- [53]R. T. Rockafellar, Convex analysis, vol. 28. Princeton university press, 1997. https://press.princeton.edu/books/paperback/9780691015866/convex-analysis.
- [54]V. Chvátal, Linear programming. Macmillan, 1983.DOI
- [55]A. Cabello, J. Estebaranz, and G. García-Alcaine, “Bell-Kochen-Specker theorem: A proof with 18 vectors,” Physics Letters A, vol. 212, no. 4, pp. 183–187, 1996. https://doi.org/10.1016/0375-9601(96)00134-X.
- [56]M. Waegell and P. Aravind, “Proofs of the Kochen–Specker theorem based on a system of three qubits,” Journal of Physics A: Mathematical and Theoretical, vol. 45, no. 40, p. 405301, 2012. https://doi.org/10.1088/1751-8113/45/40/405301.
- [57]M. Appleby, S. Flammia, G. McConnell, and J. Yard, “Sics and algebraic number theory,” Foundations of Physics, vol. 47, no. 8, pp. 1042–1059, 2017. https://doi.org/10.1007/s10701-017-0090-7.
- [58]C. Okay, “Polyhedral classical simulators for quantum computation,” Research in the Mathematical Sciences, vol. 13, no. 2, p. 55, 2026. https://doi.org/10.1007/s40687-026-00626-x.
- [59]C. Okay, W. Stern, R. Haderi, and S. Ipek, “Double categories for adaptive quantum computation,” arXiv preprint arXiv:2510.25915, 2025. https://arxiv.org/abs/2510.25915.
- [60]M. Zurel, C. Okay, and R. Raussendorf, “Simulating quantum computation: How many “bits” for “it”?,” PRX Quantum, vol. 5, no. 3, p. 030343, 2024. https://doi.org/10.1103/prxquantum.5.030343.
- [61]N. D. Mermin, “Hidden variables and the two theorems of John Bell,” Reviews of Modern Physics, vol. 65, no. 3, p. 803, 1993. https://doi.org/10.1103/RevModPhys.65.803.
- [62]C. Okay, S. Roberts, S. D. Bartlett, and R. Raussendorf, “Topological proofs of contextuality in quantum mechanics,” Quantum Information & Computation, vol. 17, no. 13-14, pp. 1135–1166, 2017. https://doi.org/10.26421/QIC17.13-14-5.
