Stabilizer operations describe a fragment of quantum theory that is known to be efficiently classically simulable, thanks to the Gottesman-Knill theorem. For this reason, nonstabilizer resources such as magic states are necessary for universal quantum computation. Interestingly, the operational and axiomatic approaches to the resource theory of magic differ: the set of free operations in the former, namely, stabilizer operations (SO), is strictly smaller than that in the latter, namely, completely stabilizer preserving operations (CSPO). A simple example showing the separation is given by a three-qubit stabilizer product basis whose states cannot be perfectly discriminated using SO, but which do admit perfect discrimination using CSPO. Such an ensemble of states is said to exhibit nonstabilizerness without magic (NSWM). Here we obtain a principled understanding of this phenomenon, proving necessary and sufficient conditions for its existence. We first derive a simple criterion to decide whether, given a stabilizer basis, its states can be perfectly discriminated using stabilizer operations alone. We then consider the case where the stabilizer basis contains only product states and use its link with process functions---classical models of paradox-free causal loops---to prove the following: the states in a stabilizer product basis require nonstabilizerness for perfect discrimination if and only if the corresponding process function violates a causal inequality. This provides a new operational meaning to causal inequality violations as witnesses of nonstabilizerness, a form of computational nonclassicality.
AI Summary
The paper asks when an orthonormal basis of stabilizer states can be perfectly distinguished using stabilizer operations (SO), and whether failures—termed nonstabilizerness without magic (NSWM)—have a causal interpretation. It treats $n$ qudits of prime local dimension $d$, including bases containing entangled states.
The first result is a necessary-and-sufficient recursive discrimination criterion. Define $\bar S_{\mathcal B}$ as the intersection of the states’ stabilizer groups modulo phases. Perfect discrimination requires a nonidentity element in this intersection; measuring its independent generators partitions the basis into smaller stabilizer-basis discrimination problems, each of which must also be solvable. The proof shows that any Pauli measurement outside the intersection destroys orthogonality between some basis states. An ancilla-removal lemma establishes that stabilizer ancillas provide no advantage.
For stabilizer product bases, the paper uses an existing correspondence with deterministic classical process functions describing logically consistent communication without an assumed causal order. It proves that SO perfectly discriminates the basis if and only if the corresponding process function is causal. Combined with the known fact that every noncausal process function violates a causal inequality, this gives an equivalence between NSWM and causal-inequality violation in this setting. The proof matches the recursive discrimination criterion to the recursive characterization of causal processes.
The results concern complete bases and perfect discrimination. Open questions include whether nonlocal SO measurements improve approximate discrimination over LOCC, and whether NSWM entangled bases exist that are not Clifford-equivalent to product bases. The causal equivalence is established only for product bases.
Little sign of AI-generated text
Error found: The abstract omits the prime-local-dimension assumption under which the paper establishes its characterization.
The ancilla-removal proof has an incorrect sign in its iterated conjugation formula and final local Pauli, but correcting these still restores the input using a local Clifford.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Stabilizer operations describe a fragment of quantum theory that is known to be efficiently classically simulable, thanks to the Gottesman-Knill theorem. For this reason, nonstabilizer resources such as magic states are necessary for universal quantum computation. Interestingly, the operational and axiomatic approaches to the resource theory of magic differ: the set of free operations in the former, namely, stabilizer operations (SO), is strictly smaller than that in the latter, namely, completely stabilizer preserving operations (CSPO). A simple example showing the separation is given by a three-qubit stabilizer product basis whose states cannot be perfectly discriminated using SO, but which do admit perfect discrimination using CSPO. Such an ensemble of states is said to exhibit nonstabilizerness without magic (NSWM). Here we obtain a principled understanding of this phenomenon, proving necessary and sufficient conditions for its existence. We first derive a simple criterion to decide whether, given a stabilizer basis, its states can be perfectly discriminated using stabilizer operations alone. We then consider the case where the stabilizer basis contains only product states and use its link with process functions---classical models of paradox-free causal loops---to prove the following: the states in a stabilizer product basis require nonstabilizerness for perfect discrimination if and only if the corresponding process function violates a causal inequality. This provides a new operational meaning to causal inequality violations as witnesses of nonstabilizerness, a form of computational nonclassicality.
The paper asks when an orthonormal basis of stabilizer states can be perfectly distinguished using stabilizer operations (SO), and whether failures—termed nonstabilizerness without magic (NSWM)—have a causal interpretation. It treats n qudits of prime local dimension d, including bases containing entangled states.
The first result is a necessary-and-sufficient recursive discrimination criterion. Define SˉB as the intersection of the states’ stabilizer groups modulo phases. Perfect discrimination requires a nonidentity element in this intersection; measuring its independent generators partitions the basis into smaller stabilizer-basis discrimination problems, each of which must also be solvable. The proof shows that any Pauli measurement outside the intersection destroys orthogonality between some basis states. An ancilla-removal lemma establishes that stabilizer ancillas provide no advantage.
For stabilizer product bases, the paper uses an existing correspondence with deterministic classical process functions describing logically consistent communication without an assumed causal order. It proves that SO perfectly discriminates the basis if and only if the corresponding process function is causal. Combined with the known fact that every noncausal process function violates a causal inequality, this gives an equivalence between NSWM and causal-inequality violation in this setting. The proof matches the recursive discrimination criterion to the recursive characterization of causal processes.
The results concern complete bases and perfect discrimination. Open questions include whether nonlocal SO measurements improve approximate discrimination over LOCC, and whether NSWM entangled bases exist that are not Clifford-equivalent to product bases. The causal equivalence is established only for product bases.
Stabilizer operations (SO) occupy a prominent role in fault-tolerant quantum computing. They are defined operationally by the use of Clifford gates, Pauli measurements, and classical control. These operations can be efficiently simulated on a classical computer, a result which is known as the Gottesman–Knill theorem. However, an additional supply of magic states is enough to promote them to a universal, fault-tolerant model for quantum computing. To quantify the needed resources in terms of magic states, a resource theory of magic has been developed. SO are considered free within this theory; however, they are not the most general class of free operations. From an axiomatic point of view, these are the completely stabilizer-preserving (CSP) channels, defined as those that preserve the convex hull of stabilizer states. It has been an open problem to decide whether these two definitions lead to the same class of operations. In this work, we answer this question in the negative, by constructing an explicit counter-example. This indicates that recently proposed stabilizer-based simulation techniques of CSP maps are strictly more powerful than Gottesman–Knill-like methods. The result is analogous to a well-known fact in entanglement theory, namely, that there is a gap between the operationally defined class of local operations and classical communication and the axiomatically defined class of separable channels.
Universal quantum computation requires non-Gaussianity in continuous-variable systems and non-stabilizerness in discrete-variable systems. Yet, mapping a Gaussian state into the Gottesman-Kitaev-Preskill logical subspace can yield a logical qubit with non-stabilizer resources. To understand how the continuous-variable structure determines logical resources, we characterize the image of single-mode Gaussian states under the corresponding extraction channel, known as the stabilizer subsystem decomposition. Specifically, we derive series expressions for the logical Bloch vector and characterize the resulting reachable set, enabling an analytical treatment of the robustness of magic of the logical states. We then turn this geometric framework into a certification tool: by mapping a discrete-variable qubit witness to a continuous-variable squeezing witness, we obtain lower bounds on the squeezing of prepared states. We also show that ensembles of Gaussian states can violate both stabilizer and classical bounds. Violation of the stabilizer bound certifies the relational resource known as "set-magic," while violation of the classical bound enables the certification of cryptographic randomness at moderate squeezing.
From both intuitive and physical perspectives, it is generally recognized that within a resource theory framework, free operations cannot broadcast a resource state due to their inability to generate resource from free states. In the stabilizer formalism of fault-tolerant quantum computation, the basic ingredients of the corresponding resource theory consist of stabilizer states as free states and stabilizer operations as free operations. The celebrated Gottesman-Knill theorem shows that quantum advantages over classical computation come from the magic (nonstabilizer) resource, such as magic states or non-Clifford gates. In this work, we prove that broadcasting of any magic state via stabilizer operations is impossible, which is reminiscent of the no-broadcasting theorems for noncommuting states or quantum correlations. We further derive a trade-off relation between the magic resource consumed in the initial system and that gained in the target system. These results characterize magic states in the stabilizer formalism from the broadcasting angle, and may have implications for distributed quantum computation and quantum secret sharing.
The stabilizer formalism plays a central role in quantum information processing and quantum computing. Since stabilizer states and operations can be efficiently simulated classically and fault-tolerantly implemented in quantum error-correcting codes, quantum states and operations beyond the stabilizer framework, characterized by nonstabilizerness or magic, naturally emerge as resources for quantum computation. Here, we demonstrate that a quantum-information task involving only stabilizer states can reveal a fundamental limitation of stabilizer operations. Specifically, we construct a set of mutually orthogonal stabilizer states that cannot be perfectly distinguished using stabilizer operations and extend this construction to an arbitrary number of qubits. Our results provide an efficient test of nonstabilizerness without requiring the direct use of resourceful states or operations nor relying on computational-hardness assumptions. This nonstabilizerness test could serve as a resource-efficient benchmark for fault-tolerant quantum computers powered by magic-state injection, by providing quantitative bounds on the robustness of magic. More fundamentally, the resulting asymmetry between the preparation and discrimination of free states parallels "nonlocality without entanglement" in entanglement theory, revealing an unexpected connection between these two distinct quantum resource theories.
In the resource theory of non-stabilizerness, we prove that stabilizer operations cannot replicate or broadcast the "magic" resource of all quantum states in an arbitrary finite dimension. Moreover, we show that even in unrestricted scenarios, there are fundamental limits on cloning the non-stabilizerness content of quantum states. When using an auxiliary system as part of the cloning process, we show that it is impossible to broadcast the non-stabilizerness of qubits that possess a greater degree of non-stabilizerness than the known states on which the transformations are based. We also derive the conditions to broadcast magic perfectly using unrestricted operations. Furthermore, we compare non-stabilizerness broadcasting with traditional state cloning methods, such as state-dependent and -independent cloners, which can achieve perfect broadcasting of states with known magic content. Our findings reveal that state-dependent cloning unitaries designed for specific states have lower average non-stabilizerness-generating power than magic-generating unitaries.
The nonstabilizerness of quantum states is a necessary resource for universal quantum computation, yet its characterization is notoriously demanding. Quantifying nonstabilizerness typically requires an exponential number of measurements and a doubly exponential classical post-processing cost to evaluate its standard monotones. In this work, we show that nonstabilizerness is, to a large extent, in the eyes of the beholder: it can be witnessed and quantified using any set of mn-qubit Pauli measurements, provided the set contains anti-commuting pairs. We introduce a general framework that projects the stabilizer polytope onto the subspace defined by these observables and provide an algorithm that estimates magic from Pauli expectation values with runtime exponential in the number of measurements m and polynomial in the number of qubits n. By relating the problem to a stabilizer-restricted variant of the quantum marginal problem, we also prove that deciding membership in the corresponding reduced stabilizer polytope is NP-hard. In particular, unless P=NP, no algorithm polynomial in m can solve the problem in full generality, thus establishing fundamental complexity-theoretic limitations. Finally, we employ our framework to compute nonstabilizerness in different Hamiltonian ground states, demonstrating the practical performance of our method in regimes beyond the reach of existing techniques.