Source-linked AI summary
The Resource Theory of Stabilizer Computation
Victor Veitch, Seyed Ali Hamed Mousavian, Daniel Gottesman, Joseph Emerson
TL;DR
The paper addresses how to characterize and quantify the non-stabilizer resources required for universal quantum computation, particularly for magic-state distillation. It develops a resource theory with two magic monotones, including a computable mana based on discrete-Wigner negativity, and uses them to derive bounds on distillation efficiency. The analysis also shows that creating arbitrary magic states from pure magic states requires a nonzero asymptotic resource ratio.
Problem
The paper addresses the need to characterize non-stabilizer resources and bound the efficiency of magic-state distillation, whose known physical resource requirements are substantial.
Method
The paper defines magic monotones under stabilizer operations and studies the relative entropy of magic together with the computable, additive mana derived from discrete-Wigner negativity.
Results
The monotones provide absolute bounds on magic-state distillation efficiency, while the relative entropy analysis establishes a nonzero asymptotic ratio of pure magic states required to create any magic state.
Takeaways & Limitations
The results distinguish the magic required to create states from the magic extractable by distillation and make discrete-Wigner negativity an operationally meaningful resource indicator.
Takeaways & Limitations
Every currently known magic-state distillation protocol has rate 0, and whether any positive-rate protocol exists remains open.
Abstract
from arXiv · showhide
Recent results on the non-universality of fault-tolerant gate sets underline the critical role of resource states, such as magic states, to power scalable, universal quantum computation. Here we develop a resource theory, analogous to the theory of entanglement, for resources for stabilizer codes. We introduce two quantitative measures - monotones - for the amount of non-stabilizer resource. As an application we give absolute bounds on the efficiency of magic state distillation. One of these monotones is the sum of the negative entries of the discrete Wigner representation of a quantum state, thereby resolving a long-standing open question of whether the degree of negativity in a quasi-probability representation is an operationally meaningful indicator of quantum behaviour.
I. INTRODUCTION
The paper frames universal quantum computation as requiring non-stabilizer resources and develops a resource theory to quantify and constrain their use. It introduces two magic monotones and applies them to magic-state distillation.
- Stabilizer operations are efficiently classically simulable and therefore must be supplemented with non-stabilizer resources for universal quantum computation.
- Magic-state computation consumes noisy non-stabilizer ancillas through stabilizer operations, distilling them into purer states suitable for gate injection.
- The resource-conversion problem asks whether ρres can produce σtarget and, if so, how many copies of ρres produce m copies of σtarget.
- Magic-state distillation can fail for broad classes of bound magic states, motivating quantitative monotone-based upper bounds on achievable efficiency.
- The paper defines magic monotones as quantities that do not increase under stabilizer operations and studies the relative entropy of magic and mana.
- The mana is computable from discrete-Wigner negativity, additive under tensor products, and yields explicit resource-count bounds for distillation.
B. Wigner Functions
The discrete Wigner representation maps quantum states and measurements to real-valued quasi-probability functions over a finite phase space. Its positivity properties connect stabilizer states and Clifford operations to classical-like descriptions.
- A discrete Wigner representation assigns each state a quasi-probability distribution over a finite phase space with (d^n)^2 points.
- The representation is real-valued because the phase-space point operators are Hermitian.
- Measurements are represented by conditional quasi-probability functions for each POVM outcome.
- When a measurement representation is nonnegative, it can be interpreted as a classical fuzzy measurement over phase-space locations.
- A state has positive representation exactly when all its Wigner values are nonnegative; otherwise it has negative representation.
- Pure states with positive representation are precisely stabilizer states, while Clifford unitaries act as phase-space permutations.
C. Magic Monotones
The paper defines magic as non-stabilizerness and formalizes stabilizer protocols as the free operations of the resource theory. A magic monotone must be non-increasing on average under those protocols.
- A magic state is a quantum state that is not a stabilizer state.
- A stabilizer protocol is a map composed from stabilizer operations, including adding stabilizer states, computational-basis measurement, and classical conditioning.
- Magic-state distillation protocols are an important special case of stabilizer protocols.
- A magic monotone maps density operators to real numbers and must not increase on average under any stabilizer protocol.
- Postselected measurements may increase a conditional branch's magic provided the average monotone over outcomes does not increase.
- Magic monotones need not be convex, because the definition constrains mixtures generated through stabilizer operations rather than all density-matrix mixtures.
III. RELATIVE ENTROPY OF MAGIC
The paper introduces relative entropy of magic as a resource monotone and studies its asymptotic behavior, while highlighting computational obstacles for explicit finite-resource distillation bounds. These limitations motivate computable alternatives.
- Resource theories generally admit multiple monotones, so the paper studies relative entropy distance to stabilizer states as one candidate for magic conversion analysis.
- The relative entropy of magic is rM(ρ) = minσ∈STAB(Hd) S(ρ∥σ), the minimum relative entropy distance from ρ to a stabilizer state.
- The relative entropy of magic is a magic monotone because relative entropy has the required monotonicity properties.
- Subadditivity means the magic added by another copy can depend on how many copies are already present, motivating regularization in the asymptotic regime.
- The relative entropy approach is difficult to use for explicit distillation bounds because its regularized form lacks a known analytic or numerical evaluation method.
- Twirling can exploit structure in commonly used resource states and permits exact evaluation for certain single-qudit forms, but does not by itself resolve multiqudit numerical problems.
- The relative entropy of magic is not generally additive, contrary to the desirable expectation that n copies contain n times the single-copy resource.
B. The (regularized) relative entropy of magic is faithful
The paper shows that regularized relative entropy of magic is faithful and characterizes asymptotic reversible conversion rates when such conversion is possible.
- Faithfulness: r∞_M(ρ) = 0 if and only if ρ is a stabilizer state.Faithfulness means the regularized measure remains nonzero for every magic state.
- Faithfulness: The proof uses stabilizer measurements and partial trace to establish faithfulness of the regularized relative entropy.A restricted-measurement relative entropy lower-bounds the usual relative entropy of magic.
- Asymptotic interconversion: Asymptotic conversion requires protocols whose approximation error tends to zero while producing m(n) copies from n input copies.The conversion rate is defined for a family of protocols with vanishing trace-distance error.
- Scope: The rate theorem is conditional because asymptotic reversible interconversion is not guaranteed, and all currently known distillation protocols have rate 0.Whether any positive-rate magic-state distillation protocol exists remains open.
- Asymptotic interconversion: If magic states ρ and σ are asymptotically reversibly interconvertible, R(ρ → σ) = r∞_M(ρ)/r∞_M(σ).The rate formula applies when the target’s regularized relative entropy is nonzero.
D. Discussion
The discussion contrasts the broad asymptotic insight of relative entropy with the practical needs of finite-resource, one-way distillation, motivating the computable mana monotone and its efficiency bounds.
- Discussion: Finite-resource one-way distillation requires a computable measure because regularized relative entropy is generally unavailable for explicit efficiency bounds.The regularized quantity is not known how to compute and is poorly suited to particular distillation protocols.
- A. Sum negativity and mana: The sum of negative discrete-Wigner entries is a magic monotone, formalizing negativity as an operationally meaningful resource indicator.Earlier work only established negativity as a binary necessary condition for distillability; this measure captures its degree.
- A. Sum negativity and mana: The Wigner absolute-value quantity is multiplicative under tensor products, motivating a logarithmic transformation of sum negativity.The composition law makes raw sum negativity scale exponentially with the number of resource states.
- A. Sum negativity and mana: The mana is a magic monotone and is additive, making it suitable for deriving simple distillation-efficiency bounds.Additivity converts monotonicity into a direct resource-accounting constraint.
- A. Sum negativity and mana: Any probabilistic protocol producing m copies of σ from ρ requires E[n] ≥ m M(σ)/M(ρ) resource copies on average.The bound applies to nested and broader protocol classes, including protocols that recycle failed outputs.
- A. Sum negativity and mana: Mana can be computed directly from the discrete Wigner function, enabling numerical upper bounds on distillation efficiency.The computation uses traces with the d^2 phase-space point operators.
B. Uniqueness of sum negativity
The paper shows that, under specified assumptions, magic monotones based only on negative Wigner values reduce to functions of the sum negativity. The result relies on stabilizer-state invariance and leaves open whether arbitrary phase-space permutation invariance is necessary.
- Uniqueness of sum negativity: The maximal Wigner negativity is not a magic monotone because composing with a stabilizer state can decrease it and increase it under partial trace.For ρ ⊗ I_d/d, maxneg scales as maxneg(ρ)/d^2.
- Uniqueness of sum negativity: Invariance under composition with arbitrary stabilizer states is the key requirement supporting the uniqueness argument for sum negativity.This invariance prevents a resource measure from changing merely because stabilizer ancillas are added.
- Uniqueness of sum negativity: Under Theorem 15’s assumptions, any magic monotone determined only by negative Wigner values and invariant under arbitrary phase-space permutations is a function solely of sum negativity.The proof constructs stabilizer ancillas so states with equal sum negativity have matching negative Wigner entries.
- Uniqueness of sum negativity: The uniqueness theorem assumes invariance under arbitrary phase-space permutations, beyond the Clifford-induced permutations, and the necessity of this assumption remains unresolved.The paper identifies proving uniqueness without this assumption or finding a position-dependent counterexample as an open problem.
- Uniqueness of sum negativity: Mana is not asymptotically continuous, while it remains open whether the weaker condition needed for explicit asymptotic conversion rates holds.Consequently, the theorem does not currently yield explicit conversion rates from mana alone.
C. Numerical Analysis of Magic State Distillation Protocols
The paper numerically evaluates several qudit magic-state distillation protocols by comparing input mana with effective output mana after one protocol round. Across the examined qutrit and ququint codes, none approaches the mana bound.
- C. Numerical Analysis of Magic State Distillation Protocols: None of the evaluated distillation protocols comes close to the mana bound shown in the figures.The comparison covers qutrit codes from [1] and and a ququint code from.
- C. Numerical Analysis of Magic State Distillation Protocols: For the [[5, 1, 3]]3 qutrit code, 50000 twirled inputs are compared by input mana and effective output mana after one protocol round.Effective output mana is E[M(ρout)] = Pr(protocol succeeds) · M(ρout), with p1 ∈R [0, 0.4] and p2 ∈R [0, 0.3].
- C. Numerical Analysis of Magic State Distillation Protocols: For the [[8, 1, 3]]3 qutrit code, 50000 twirled inputs are evaluated using the same input-versus-effective-output mana comparison.The sampled parameters satisfy p1 ∈R [0, 0.3] and p2 ∈R [0, 0.3].
- C. Numerical Analysis of Magic State Distillation Protocols: For the [[4, 1, 2]]5 ququint code, 50000 twirled inputs are likewise assessed through input and effective output mana.The input family is parameterized by four probabilities after twirling.
D. The Qutrit Case
The qutrit analysis identifies two distinct classes of states with maximal sum negativity and characterizes their geometric locations relative to the Wigner simplex. Both classes attain the same maximum value.
- D. The Qutrit Case: Two classes of maximally sum-negative qutrit states emerge from an exhaustive search over subsets of discrete phase space.The search identifies states with distinct patterns of negative Wigner entries.
- D. The Qutrit Case: +1/3 is the maximum sum negativity, attained by both Strange and Norrell qutrit states.The paper gives sn(|S⟩⟨S|) = sn(|N⟩⟨N|) = +1/3.
- D. The Qutrit Case: Geometrically, Strange states lie outside one Wigner-simplex face, whereas Norrell states lie outside the intersection of two faces.The paper relates these locations to qutrit analogues of qubit T-type and H-type states.
- D. The Qutrit Case: Figure 4 compares the Wigner representations of representative Strange and Norrell states, while Figure 5 displays mana over a two-parameter state plane.The Figure 5 heat map marks the zero-mana Wigner-simplex region and the stabilizer polytope boundary.
E. Wherefore the discrete Wigner function?
The paper motivates discrete-Wigner-based magic monotones through their links to classical simulation, contextuality, and distillation, while situating them within a broader resource-theoretic framework.
- Positive discrete-Wigner states form a maximal classical subtheory, with negativity onset connected to contextuality violation in small prime dimensions.Recent work links Wigner negativity to non-contextuality violation and shows that positive-Wigner states support a classical hidden-variable description.
- The Wigner representation naturally supports efficient classical simulation of stabilizer circuits with positive Wigner representations, although negativity alone is not known to guarantee universality.
- Mana is essentially the unique symmetric monotone arising from Wigner negativity, reflecting the special role of the discrete Wigner representation.
- A qubit analogue of mana remains unresolved because qubit stabilizers can violate contextuality inequalities, preventing a discrete-Wigner-function analogue.
- The resource theory introduces magic monotones, including relative entropy of magic and mana, by analogy with entanglement theory.
- Mana provides computable bounds on magic-state conversion rates, addressing the relative entropy of magic’s lack of a closed form.The relative entropy of magic is useful asymptotically but generally requires numerical computation; mana was introduced to provide an explicitly computable alternative.
Appendix A: Proofs on the relative entropy of magic
The appendix establishes that relative entropy of magic and its regularization are monotones under stabilizer operations, with the regularized quantity faithfully detecting non-stabilizer states.
- The relative entropy of magic is a magic monotone, remaining non-increasing under stabilizer operations.
- Stabilizer measurements do not increase relative entropy of magic on average because normalized post-measurement stabilizer states remain stabilizer states.
- Partial trace and composition with arbitrary quantum states preserve the monotonicity requirements through relative-entropy inequalities and partial-trace monotonicity.
- The regularized relative entropy of magic is zero exactly for states expressible as convex combinations of stabilizer states.
- The regularized quantity is positive for magic states because stabilizer measurements include an informationally complete measurement.
Appendix B: Proofs on sum negativity and mana
The appendix proves that the Wigner-function 1-norm is a convex magic monotone and that any symmetric monotone depending only on Wigner negativity reduces to sum negativity.
- ∥ρ∥W = P_u |Wρ(u)| is a convex magic monotone.
- The Wigner-function 1-norm is preserved by Clifford permutations and does not increase under stabilizer measurements, composition with positive-Wigner states, or partial trace.
- Any magic monotone determined only by negative Wigner values and invariant under arbitrary phase-space permutations is a function solely of sum negativity.
- Ancilla constructions match the negative-entry distributions of states with equal total negativity, establishing that the monotone cannot depend on more than sum negativity.
- The appendix uses tensor-product ancillas to reproduce paired negative-entry values while preserving the relevant Wigner distributions.
2. Continuity and Asymptotic Continuity
The paper distinguishes approximate asymptotic conversion from perfect conversion and proves that mana is not asymptotically continuous because rare, highly resourceful outputs can change its value substantially.
- Perfect conversion is generally unavailable, so approximate conversion permits outputs within trace distance ϵ of the target tensor power.
- The continuity issue matters because asymptotic continuity would have allowed mana to determine asymptotic conversion rates, as the regularized relative entropy does.
- Mana is not asymptotically continuous.
- A vanishing-probability mixture with a state of greater negativity can prevent the continuity limit from approaching zero.
- Rare access to a very large amount of resource can dramatically improve a preparation procedure, explaining the failure of asymptotic continuity.