Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Hot Logic: A Complete Resource Theory of Magic via the Origami ISA

Ian Richard C Buckley

Published Jun 27, 2026• 0 citations
Publisher

Abstract

Standard quantum resource theory uses Wigner negativity $\mathcal{N} > 0$ as its resource indicator for magic states. We show this is incomplete: there exist states outside the stabiliser polytope with $\mathcal{N} = 0$, which we call dark magic. These states are undetectable by the standard monotone yet are non-stabiliser by every other measure. The Origami ISA rewrite system $\mathcal{R} = {R3, R4}$ (completeness proved in companion Paper 469) partitions the single-phase 3-qubit fragment $\mathcal{F}$ into exactly 9 normal-form classes in three tiers: Tier Class $\mathrm{TV}$ $\mathcal{N}$ 0 Stabiliser (1 class) $= 1$ $= 0$ 1 Dark magic (6 classes) $< 1$ $= 0$ 2 Genuine magic (2 classes) $< 1$ $> 0$ Theorem 1 (TV monotone). The total variation $\mathrm{TV}(\psi) = \sum_u |W_\psi(u)|$ of the discrete Wigner function is a complete resource monotone on $\mathcal{F}$: $\mathrm{TV}(\psi) = 1$ if and only if $\psi$ is a stabiliser state. Wigner negativity $\mathcal{N} = \frac{1}{2}(\mathrm{TV} - 1)$ vanishes on all of Tier 1, so it is merely sufficient (Tier 2) but not complete. Theorem 2 (Three-tier completeness). The tier of any state in $\mathcal{F}$ is decidable at compile time: apply R3 (T-absorption counit) — if the T gate is absorbed the state is Tier 0; otherwise compute $\mathrm{TV}$ from the 9-entry precomputed table. Corollary (Distillation failure mode). A magic-state distillation protocol using $\mathcal{N}$ as its sole convergence criterion may silently converge to a dark-magic state (Tier 1, $\mathcal{N} = 0$, $\mathrm{TV} < 1$) and declare success. The fix: require $\mathrm{TV} = 1$ as the termination criterion. Dark magic occupies the tropical boundary of the MGE $\beta$-ladder: Tier 1 states are quantum in structure ($\mathrm{TV} < 1$) but classical in Wigner measure ($\mathcal{N} = 0$), exactly at the Maslov dequantisation saddle point $\beta \to 0$. Part of the Origami ISA series. Companion papers: 466 (CZ-type bases) · 467 (magic orbits) · 468 (ISA as coloured PROP) · 469 (completeness theorem) Keywords: quantum resource theory, magic states, dark magic, Wigner negativity, total variation, stabiliser states, Clifford hierarchy, Origami ISA, rewrite systems, normal forms, magic state distillation, tropical geometry, Maslov dequantisation, coloured PROP

DOI
10.5281/zenodo.20956685

Related papers

Dark Magic: A Complete Resource Theory of Magic via the Origami ISA

Ian Richard C Buckley

Develops a complete resource theory of magic using the Origami ISA. Introduces 'dark magic' — states with negative Wigner function that are nonetheless efficiently simulable — and shows the total variation distance is the correct discriminant separating stabiliser, dark-magic, and genuinely magic tiers. Connects magic resource theory to the ISA beta parameter and the tropical/Clifford/metaplectic H^k complexity ladder.

•Jul 6, 2026•0 citations

Resource Theory as Circuit Syntax: The Origami ISA as a Coloured PROP [WITHDRAWN — depends on withdrawn results]

Ian Richard C Buckley

WITHDRAWN BY THE AUTHOR (2026-08-02). This record should not be cited. Fileshave been restricted. --- Why --- The paper proposes reading quantum resource theory syntactically, as a colouredproduct-and-permutation category (coloured PROP), with the Clifford-hierarchylevels C1/C2/C3 as colours and resource cost as the minimum C3-gate count in anormal form. Two of its load-bearing inputs have since been withdrawn, and oneof them carries an error that this paper inherits verbatim. 1. THE TOTAL-VARIATION GRADING IS BASED ON A SIGN ERROR. The paper defines"dark magic" as states that are non-stabiliser yet have zero Wigner negativityand total variation TV < 1, and states (Sec. 6) that TV(p) = 1 if and only if pis a free state. This is incorrect. For any quasi-probability distributionsumming to 1, the l1 norm satisfies Sum |W| >= 1 always, with equality exactlywhen W is non-negative. Direct computation: the stabiliser state |+> givesTV = 1.0000, and the magic state T|+> gives TV = 1.2071. The inequality runsthe other way, so the condition "TV < 1" describes the empty set and the"dark magic" tier as defined has no members. The source of this definition(a companion paper on magic resource theory) has been withdrawn for the samereason. Separately, TV as defined is exp(mana), a monotone reparameterisationof the established Wigner-negativity monotone of Veitch, Mari, Ferrie, Emersonand others, and was not compared against it. 2. THE WORKED EXAMPLES NO LONGER EXIST. Every worked example in the paper isone of the "9 magic orbit classes" of a companion paper that has since beenwithdrawn because its own experiment scripts did not reproduce its claims(printing FAILED for the orbit-inheritance theorem, and fidelity 0.000000against a claimed value of 1/4, with 8 classes printed where 9 were claimed).Two further companion papers cited for the rewrite-rule and normal-formresults have also been withdrawn. 3. NO COMPUTATIONS WERE PERFORMED. There is no experiment directory associatedwith this paper. --- What was not wrong --- The organising idea -- that a resource theory can be presented syntactically,with resource tier readable from a diagram -- is reasonable and is not thereason for withdrawal. But the specific cost measure proposed (minimum C3-gatecount) is T-count, a standard and well-studied quantity (Amy, Maslov and Mosca;Gosset, Kliuchnikov, Mosca and Russo, and subsequent work), and gradedcategorical presentations of Clifford+T are the subject of the ZX-calculuscompleteness literature (Jeandel, Perdrix and Vilmart 2018 and successors).Neither literature is engaged here. A future treatment would need to start fromthose. Readers wanting the correct treatment of the underlying physics should consultVeitch et al. on Wigner negativity and mana, Howard and Campbell on robustnessof magic, and the ZX-calculus completeness results cited above.

•Jun 27, 2026•0 citations

Associamancy: A Resource Theory of Non-Associative Quantum Magic

Ian Richard C Buckley

PENDING QUALITY AUDIT (2026-08). The file is restricted while this record is reviewed as part of a systematic audit of the author's corpus. It has not yet been assessed. Metadata and DOI remain public, and access can be requested. The resource theory of quantum magic (Veitch et al. 2014) identifies non-stabiliser states as resources and T-gates as the elementary injection operation. Subsequent work established that the magic sector itself splits into two sub-tiers: dark magic (Wigner-negative but TV = 1, Clifford-simulable under reframing) and genuine magic (TV < 1), where TV is the total variation of the discrete Wigner function. We identify a strictly richer resource — associamancy — that sits above both sub-tiers and that standard magic theory cannot see, cannot create from below, and cannot measure without the SPIN opcode of the 731 ISA. The boundary is algebraically precise. A quantum state possesses associamancy if and only if its hidden symmetry group contains an irreducible representation with Frobenius-Schur indicator ν₂ = 0 — the condition that the representation is genuinely complex, realisable over ℂ but not over ℝ or ℍ. We call this the Schur boundary. Three equivalent characterisations of the Schur boundary are established: (1) Algebraic: ν₂(V_λ) = 0 for some irrep V_λ of the hidden symmetry group. (2) Cohomological: the obstruction class [α] ≠ 0 ∈ H²(G, U(1)) is non-trivial. (3) Number-theoretic: for G = PSL(2,q), associamancy holds if and only if q ≡ 3 (mod 4) — the same condition that makes the quadratic Gauss sum τ(q) = i√q purely imaginary. The Schur entropy S_Schur(|ψ⟩) = −∑_{λ:ν₂=0} p_λ log p_λ is a valid resource monotone, independent of both Wigner negativity and TV: a state can have TV ≪ 1 (genuine magic) and zero Schur entropy, and a state can have S_Schur = log 2 at either dark or genuine magic level. PSL(2,7) is the minimal group exhibiting associamancy (order 168). The Freudenthal magic square organises associamancy into a ladder G₂ ⊂ F₄ ⊂ E₆ ⊂ E₇ ⊂ E₈, each rung strictly richer than the last. Keywords: quantum resource theory, magic states, associamancy, Frobenius-Schur indicator, Schur boundary, non-associative, octonions, PSL(2,7), Freudenthal magic square, G₂, 731 ISA, dark magic, total variation, quantum computing

•Jun 12, 2026•0 citations

The Wigner Defect Conservation Law: $N$-Independence of Magic Imprinted by a Single $T$ Gate

Ian Richard C Buckley

We prove that the discrete Wigner function of the canonical $N$-qubit state $|\psi_N\rangle = \mathrm{CZ}{01}\cdot(T\otimes I^{\otimes N-1})\cdot|{+}^{\otimes N}\rangle$ satisfies an exact conservation law for all $N \geq 2$. Three quantities are independent of system size: the total negative Wigner mass $\sum{W<0} W_N(u) = -\sqrt{2}/8$, the total Wigner mass $\sum_u W_N(u) = \cos^2(\pi/8) = (2+\sqrt{2})/4$, and the total variation $\sum_u |W_N(u)| = (1+\sqrt{2})/2$. The conserved quantity $(1+\sqrt{2})/2 = \delta_S/2$, where $\delta_S = 1+\sqrt{2}$ is the silver ratio, reflects the $T$-gate angle $\pi/4$ via the half-angle identity $\cos^2(\pi/8) = (2+\sqrt{2})/4$. The $T$ gate imprints a fixed Wigner defect of magnitude $\sqrt{2}/8$ into phase space; adding $|{+}\rangle$ spectator qubits spreads this defect across $2^{N-2}$ cells but never changes its total. The conservation follows from the factorisation $W_N = W_2 \otimes W_{|+\rangle}^{\otimes N-2}$ and the fact that $\sum_u W_{|+\rangle}(u) = 1$ exactly for any stabiliser state. The conserved constants $\cos^2(\pi/8)$ and $(1+\sqrt{2})/2$ are the tier-boundary constants of the three-tier magic resource theory (Buckley 2026, Hot Logic). The conservation law explains why these constants are fundamental: they are $N$-independent invariants of the entire single-$T$ family, not properties of any specific state. The dark-magic tier is stable under adding spectator qubits. All five quantities are confirmed to machine precision for $N = 2, 3, 4, 5, 6$ by experiment x471b. Keywords: Wigner function · magic states · resource theory · T gate · stabiliser states · discrete Wigner function · silver ratio · conservation law · Clifford hierarchy · quantum computation · Origami ISA · dark magic

•Jun 27, 2026•0 citations

The unbearable hardness of deciding about magic

Lorenzo Leone, Jens Eisert, Salvatore F. E. Oliviero

Identifying the boundary between classical and quantum computation is a central challenge in quantum information. In multi-qubit systems, entanglement and magic are the key resources underlying genuinely quantum behaviour. While entanglement is well understood, magic - essential for universal quantum computation - remains relatively poorly characterised. Here we show that determining membership in the stabilizer polytope, which defines the free states of magic-state resource theory, requires super-exponential time $\class{exp} ( n^2)$ in the number of qubits $n$, even approximately. We reduce the problem to solving a $3$-\class{SAT} instance on $n^2$ variables and, by invoking the exponential time hypothesis, the result follows. As a consequence, both quantifying and certifying magic are fundamentally intractable: any magic monotone for general states must be super-exponentially hard to compute, and deciding whether an operator is a valid magic witness is equally difficult. As a corollary, we establish the robustness of magic as computationally optimal among monotones. This barrier extends even to classically simulable regimes: deciding whether a state lies in the convex hull of states generated by a logarithmic number of non-Clifford gates is also super-exponentially hard. Together, these results reveal intrinsic computational limits on assessing classical simulability, distilling pathological magic states, and ultimately probing and exploiting magic as a quantum resource.

quant-pharXiv:2602.22330•Feb 27, 2026•0 citations

A Phase-Space Geometric Measure of Magic in Qubit Systems

Soumyojyoti Dutta, Tushar

Magic -- the resource enabling quantum computational advantage beyond stabilizer circuits -- has a clean phase-space characterization in odd prime dimensions that qubits notoriously lack. We study C(rho), the l_1 distance from a state's discrete Wigner function to the stabilizer polytope, and determine its exact geometry. For a single qubit with Bloch vector r we prove the closed form C = max(0, ||r||_1 - 1)/2, so the maximum is (sqrt(3)-1)/2, attained at the eight face states. For products of single-qubit states, C(rho_1 x ... x rho_n) <= prod_i (1 + C(rho_i)) - 1, with equality whenever every factor has Bloch sign product r_x r_y r_z <= 0; this includes the exact tensor powers ((1+sqrt(3))/2)^n - 1 and the exact maximum of C over fully separable n-qubit states. Because no discrete Wigner function for qubits is Clifford covariant, any such measure is frame dependent, and we identify which of its features are not. For a single qubit there are exactly two valid frames up to phase-space translation and C is identical on both. Pauli-covariant two-qubit frames number 2048 up to translation, and across them the ratio C(rho_Rx)/C(rho_Ry) takes the values 1/2, 1 and 2. In every one of these frames some stabilizer state has negative Wigner entries, a consequence of the Mermin-Peres square, so the two-qubit bound Gamma >= 1 + C/2 against the robustness of magic Gamma is frame independent. Within the Wootters frame we prove integer values 1, 2, 1 of the tightness ratio kappa := (Gamma-1)/C for three families in the two-qubit repetition codespace, with explicit certificates. For n-qubit GHZ phase states we prove Gamma = |sin phi| + |cos phi| for all n and C >= 2^(floor(n/2)-1) (|sin phi| + |cos phi| - 1), tight for n = 2 and, by exact linear programming, for n = 3, 4, so kappa decays exponentially. Finally, C is not a magic monotone, so it cannot replace Gamma in distillation bounds.

quant-pharXiv:2603.20792•Mar 24, 2026•0 citations
Standard quantum resource theory uses Wigner negativity N>0\mathcal{N} > 0N>0 as its resource indicator for magic states. We show this is incomplete: there exist states outside the stabiliser polytope with N=0\mathcal{N} = 0N=0, which we call dark magic. These states are undetectable by the standard monotone yet are non-stabiliser by every other measure. The Origami ISA rewrite system R=R3,R4\mathcal{R} = {R3, R4}R=R3,R4 (completeness proved in companion Paper 469) partitions the single-phase 3-qubit fragment F\mathcal{F}F into exactly 9 normal-form classes in three tiers: Tier Class TV\mathrm{TV}TV N\mathcal{N}N 0 Stabiliser (1 class) =1= 1=1 =0= 0=0 1 Dark magic (6 classes) <1< 1<1 =0= 0=0 2 Genuine magic (2 classes) <1< 1<1 >0> 0>0 Theorem 1 (TV monotone). The total variation TV(ψ)=∑u∣Wψ(u)∣\mathrm{TV}(\psi) = \sum_u |W_\psi(u)|TV(ψ)=∑u​∣Wψ​(u)∣ of the discrete Wigner function is a complete resource monotone on F\mathcal{F}F: TV(ψ)=1\mathrm{TV}(\psi) = 1TV(ψ)=1 if and only if ψ\psiψ is a stabiliser state. Wigner negativity N=12(TV−1)\mathcal{N} = \frac{1}{2}(\mathrm{TV} - 1)N=21​(TV−1) vanishes on all of Tier 1, so it is merely sufficient (Tier 2) but not complete. Theorem 2 (Three-tier completeness). The tier of any state in F\mathcal{F}F is decidable at compile time: apply R3 (T-absorption counit) — if the T gate is absorbed the state is Tier 0; otherwise compute TV\mathrm{TV}TV from the 9-entry precomputed table. Corollary (Distillation failure mode). A magic-state distillation protocol using N\mathcal{N}N as its sole convergence criterion may silently converge to a dark-magic state (Tier 1, N=0\mathcal{N} = 0N=0, TV<1\mathrm{TV} < 1TV<1) and declare success. The fix: require TV=1\mathrm{TV} = 1TV=1 as the termination criterion. Dark magic occupies the tropical boundary of the MGE β\betaβ-ladder: Tier 1 states are quantum in structure (TV<1\mathrm{TV} < 1TV<1) but classical in Wigner measure (N=0\mathcal{N} = 0N=0), exactly at the Maslov dequantisation saddle point β→0\beta \to 0β→0. Part of the Origami ISA series. Companion papers: 466 (CZ-type bases) · 467 (magic orbits) · 468 (ISA as coloured PROP) · 469 (completeness theorem) Keywords: quantum resource theory, magic states, dark magic, Wigner negativity, total variation, stabiliser states, Clifford hierarchy, Origami ISA, rewrite systems, normal forms, magic state distillation, tropical geometry, Maslov dequantisation, coloured PROP
WITHDRAWN BY THE AUTHOR (2026-08-02). This record should not be cited. Fileshave been restricted. --- Why --- The paper proposes reading quantum resource theory syntactically, as a colouredproduct-and-permutation category (coloured PROP), with the Clifford-hierarchylevels C1/C2/C3 as colours and resource cost as the minimum C3-gate count in anormal form. Two of its load-bearing inputs have since been withdrawn, and oneof them carries an error that this paper inherits verbatim. 1. THE TOTAL-VARIATION GRADING IS BASED ON A SIGN ERROR. The paper defines"dark magic" as states that are non-stabiliser yet have zero Wigner negativityand total variation TV < 1, and states (Sec. 6) that TV(p) = 1 if and only if pis a free state. This is incorrect. For any quasi-probability distributionsumming to 1, the l1 norm satisfies Sum |W| >= 1 always, with equality exactlywhen W is non-negative. Direct computation: the stabiliser state |+> givesTV = 1.0000, and the magic state T|+> gives TV = 1.2071. The inequality runsthe other way, so the condition "TV < 1" describes the empty set and the"dark magic" tier as defined has no members. The source of this definition(a companion paper on magic resource theory) has been withdrawn for the samereason. Separately, TV as defined is exp(mana), a monotone reparameterisationof the established Wigner-negativity monotone of Veitch, Mari, Ferrie, Emersonand others, and was not compared against it. 2. THE WORKED EXAMPLES NO LONGER EXIST. Every worked example in the paper isone of the "9 magic orbit classes" of a companion paper that has since beenwithdrawn because its own experiment scripts did not reproduce its claims(printing FAILED for the orbit-inheritance theorem, and fidelity 0.000000against a claimed value of 1/4, with 8 classes printed where 9 were claimed).Two further companion papers cited for the rewrite-rule and normal-formresults have also been withdrawn. 3. NO COMPUTATIONS WERE PERFORMED. There is no experiment directory associatedwith this paper. --- What was not wrong --- The organising idea -- that a resource theory can be presented syntactically,with resource tier readable from a diagram -- is reasonable and is not thereason for withdrawal. But the specific cost measure proposed (minimum C3-gatecount) is T-count, a standard and well-studied quantity (Amy, Maslov and Mosca;Gosset, Kliuchnikov, Mosca and Russo, and subsequent work), and gradedcategorical presentations of Clifford+T are the subject of the ZX-calculuscompleteness literature (Jeandel, Perdrix and Vilmart 2018 and successors).Neither literature is engaged here. A future treatment would need to start fromthose. Readers wanting the correct treatment of the underlying physics should consultVeitch et al. on Wigner negativity and mana, Howard and Campbell on robustnessof magic, and the ZX-calculus completeness results cited above.
PENDING QUALITY AUDIT (2026-08). The file is restricted while this record is reviewed as part of a systematic audit of the author's corpus. It has not yet been assessed. Metadata and DOI remain public, and access can be requested. The resource theory of quantum magic (Veitch et al. 2014) identifies non-stabiliser states as resources and T-gates as the elementary injection operation. Subsequent work established that the magic sector itself splits into two sub-tiers: dark magic (Wigner-negative but TV = 1, Clifford-simulable under reframing) and genuine magic (TV < 1), where TV is the total variation of the discrete Wigner function. We identify a strictly richer resource — associamancy — that sits above both sub-tiers and that standard magic theory cannot see, cannot create from below, and cannot measure without the SPIN opcode of the 731 ISA. The boundary is algebraically precise. A quantum state possesses associamancy if and only if its hidden symmetry group contains an irreducible representation with Frobenius-Schur indicator ν₂ = 0 — the condition that the representation is genuinely complex, realisable over ℂ but not over ℝ or ℍ. We call this the Schur boundary. Three equivalent characterisations of the Schur boundary are established: (1) Algebraic: ν₂(V_λ) = 0 for some irrep V_λ of the hidden symmetry group. (2) Cohomological: the obstruction class [α] ≠ 0 ∈ H²(G, U(1)) is non-trivial. (3) Number-theoretic: for G = PSL(2,q), associamancy holds if and only if q ≡ 3 (mod 4) — the same condition that makes the quadratic Gauss sum τ(q) = i√q purely imaginary. The Schur entropy S_Schur(|ψ⟩) = −∑_{λ:ν₂=0} p_λ log p_λ is a valid resource monotone, independent of both Wigner negativity and TV: a state can have TV ≪ 1 (genuine magic) and zero Schur entropy, and a state can have S_Schur = log 2 at either dark or genuine magic level. PSL(2,7) is the minimal group exhibiting associamancy (order 168). The Freudenthal magic square organises associamancy into a ladder G₂ ⊂ F₄ ⊂ E₆ ⊂ E₇ ⊂ E₈, each rung strictly richer than the last. Keywords: quantum resource theory, magic states, associamancy, Frobenius-Schur indicator, Schur boundary, non-associative, octonions, PSL(2,7), Freudenthal magic square, G₂, 731 ISA, dark magic, total variation, quantum computing
The Wigner Defect Conservation Law: NNN-Independence of Magic Imprinted by a Single TTT Gate
We prove that the discrete Wigner function of the canonical NNN-qubit state ∣ψN⟩=CZ01⋅(T⊗I⊗N−1)⋅∣+⊗N⟩|\psi_N\rangle = \mathrm{CZ}{01}\cdot(T\otimes I^{\otimes N-1})\cdot|{+}^{\otimes N}\rangle∣ψN​⟩=CZ01⋅(T⊗I⊗N−1)⋅∣+⊗N⟩ satisfies an exact conservation law for all N≥2N \geq 2N≥2. Three quantities are independent of system size: the total negative Wigner mass ∑W<0WN(u)=−2/8\sum{W<0} W_N(u) = -\sqrt{2}/8∑W<0WN​(u)=−2​/8, the total Wigner mass ∑uWN(u)=cos⁡2(π/8)=(2+2)/4\sum_u W_N(u) = \cos^2(\pi/8) = (2+\sqrt{2})/4∑u​WN​(u)=cos2(π/8)=(2+2​)/4, and the total variation ∑u∣WN(u)∣=(1+2)/2\sum_u |W_N(u)| = (1+\sqrt{2})/2∑u​∣WN​(u)∣=(1+2​)/2. The conserved quantity (1+2)/2=δS/2(1+\sqrt{2})/2 = \delta_S/2(1+2​)/2=δS​/2, where δS=1+2\delta_S = 1+\sqrt{2}δS​=1+2​ is the silver ratio, reflects the TTT-gate angle π/4\pi/4π/4 via the half-angle identity cos⁡2(π/8)=(2+2)/4\cos^2(\pi/8) = (2+\sqrt{2})/4cos2(π/8)=(2+2​)/4. The TTT gate imprints a fixed Wigner defect of magnitude 2/8\sqrt{2}/82​/8 into phase space; adding ∣+⟩|{+}\rangle∣+⟩ spectator qubits spreads this defect across 2N−22^{N-2}2N−2 cells but never changes its total. The conservation follows from the factorisation WN=W2⊗W∣+⟩⊗N−2W_N = W_2 \otimes W_{|+\rangle}^{\otimes N-2}WN​=W2​⊗W∣+⟩⊗N−2​ and the fact that ∑uW∣+⟩(u)=1\sum_u W_{|+\rangle}(u) = 1∑u​W∣+⟩​(u)=1 exactly for any stabiliser state. The conserved constants cos⁡2(π/8)\cos^2(\pi/8)cos2(π/8) and (1+2)/2(1+\sqrt{2})/2(1+2​)/2 are the tier-boundary constants of the three-tier magic resource theory (Buckley 2026, Hot Logic). The conservation law explains why these constants are fundamental: they are NNN-independent invariants of the entire single-TTT family, not properties of any specific state. The dark-magic tier is stable under adding spectator qubits. All five quantities are confirmed to machine precision for N=2,3,4,5,6N = 2, 3, 4, 5, 6N=2,3,4,5,6 by experiment x471b. Keywords: Wigner function · magic states · resource theory · T gate · stabiliser states · discrete Wigner function · silver ratio · conservation law · Clifford hierarchy · quantum computation · Origami ISA · dark magic
Identifying the boundary between classical and quantum computation is a central challenge in quantum information. In multi-qubit systems, entanglement and magic are the key resources underlying genuinely quantum behaviour. While entanglement is well understood, magic - essential for universal quantum computation - remains relatively poorly characterised. Here we show that determining membership in the stabilizer polytope, which defines the free states of magic-state resource theory, requires super-exponential time $\class{exp} ( n^2)$ in the number of qubits nnn, even approximately. We reduce the problem to solving a 333-\class{SAT} instance on n2n^2n2 variables and, by invoking the exponential time hypothesis, the result follows. As a consequence, both quantifying and certifying magic are fundamentally intractable: any magic monotone for general states must be super-exponentially hard to compute, and deciding whether an operator is a valid magic witness is equally difficult. As a corollary, we establish the robustness of magic as computationally optimal among monotones. This barrier extends even to classically simulable regimes: deciding whether a state lies in the convex hull of states generated by a logarithmic number of non-Clifford gates is also super-exponentially hard. Together, these results reveal intrinsic computational limits on assessing classical simulability, distilling pathological magic states, and ultimately probing and exploiting magic as a quantum resource.
Magic -- the resource enabling quantum computational advantage beyond stabilizer circuits -- has a clean phase-space characterization in odd prime dimensions that qubits notoriously lack. We study C(rho), the l_1 distance from a state's discrete Wigner function to the stabilizer polytope, and determine its exact geometry. For a single qubit with Bloch vector r we prove the closed form C = max(0, ||r||_1 - 1)/2, so the maximum is (sqrt(3)-1)/2, attained at the eight face states. For products of single-qubit states, C(rho_1 x ... x rho_n) <= prod_i (1 + C(rho_i)) - 1, with equality whenever every factor has Bloch sign product r_x r_y r_z <= 0; this includes the exact tensor powers ((1+sqrt(3))/2)^n - 1 and the exact maximum of C over fully separable n-qubit states. Because no discrete Wigner function for qubits is Clifford covariant, any such measure is frame dependent, and we identify which of its features are not. For a single qubit there are exactly two valid frames up to phase-space translation and C is identical on both. Pauli-covariant two-qubit frames number 2048 up to translation, and across them the ratio C(rho_Rx)/C(rho_Ry) takes the values 1/2, 1 and 2. In every one of these frames some stabilizer state has negative Wigner entries, a consequence of the Mermin-Peres square, so the two-qubit bound Gamma >= 1 + C/2 against the robustness of magic Gamma is frame independent. Within the Wootters frame we prove integer values 1, 2, 1 of the tightness ratio kappa := (Gamma-1)/C for three families in the two-qubit repetition codespace, with explicit certificates. For n-qubit GHZ phase states we prove Gamma = |sin phi| + |cos phi| for all n and C >= 2^(floor(n/2)-1) (|sin phi| + |cos phi| - 1), tight for n = 2 and, by exact linear programming, for n = 3, 4, so kappa decays exponentially. Finally, C is not a magic monotone, so it cannot replace Gamma in distillation bounds.