In this work, we introduce a state-space distance calibrated by stabilizer states based on the dual structure of the robustness of magic (RoM), and show that RoM is exactly represented as the distance to the free-state set. We then extend this geometry to state conversion by defining the directed conversion deficiency $C_{\mathcal F}$ as the distance between a target state and the set of states freely reachable from a given input state. The quantity $C_{\mathcal F}$ characterizes free convertibility and is related to the minimum stabilizer quasiprobability weight required to represent the conversion residual through the relation $1+2C_{\mathcal F}$. It also contains the conventional magic state resource lower bounds based on RoM and can detect stronger conversion obstructions. For single-qubit systems, we analytically construct a continuous family of mixed states with identical RoM but asymmetric convertibility.
In this work, we introduce a state-space distance calibrated by stabilizer states based on the dual structure of the robustness of magic (RoM), and show that RoM is exactly represented as the distance to the free-state set. We then extend this geometry to state conversion by defining the directed conversion deficiency CF as the distance between a target state and the set of states freely reachable from a given input state. The quantity CF characterizes free convertibility and is related to the minimum stabilizer quasiprobability weight required to represent the conversion residual through the relation 1+2CF. It also contains the conventional magic state resource lower bounds based on RoM and can detect stronger conversion obstructions. For single-qubit systems, we analytically construct a continuous family of mixed states with identical RoM but asymmetric convertibility.
Nonstabilizerness, or magic, is an essential quantum resource for performing universal quantum computation. Specifically, Robustness of Magic (RoM) characterizes the usefulness of a given quantum state for non-Clifford operations. While the mathematical formalism of RoM is concise, determining RoM in practice is highly challenging due to the necessity of dealing with a super-exponential number of stabilizer states. In this work, we present novel algorithms to compute RoM. The key technique is a subroutine for calculating overlaps between all stabilizer states and a target state, with the following remarkable features: (i) the time complexity per state is reduced {exponentially}, and (ii) the total space complexity is reduced {super-exponentially}. Based on this subroutine, we present algorithms to compute RoM for arbitrary states up to n = 8 qubits, whereas the naive method requires a memory size of at least 86 PiB , which is infeasible for any current classical computer. Additionally, the proposed subroutine enables the computation of stabilizer fidelity for a mixed state up to n = 8 qubits. We further propose novel algorithms that exploit prior knowledge of the structure of the target quantum state, such as permutation symmetry or disentanglement, and numerically demonstrate our results for copies of magic states and partially disentangled quantum states. This series of algorithms constitutes a comprehensive ``handbook'' for scaling up the computation of RoM. We envision that the proposed technique will also apply to the computation of other quantum resource measures.
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.
Magic plays a dual role in quantum computation: it promotes stabilizer dynamics from efficient classical simulability to computational universality, but also challenges fault-tolerant architectures, since non-stabilizer operations are harder to protect against noise. Magic state distillation addresses this issue, yet existing protocols remain largely tailored to specific assumptions about the input or noise model and, more fundamentally, no general information-theoretic theory of optimal magic-state conversion currently exists. Here we develop such a characterization for pure qubit states through universal magic state concentration: a fixed stabilizer protocol that converts a few copies of an unknown pure non-stabilizer qubit state into an exact target magic state. Motivated by the impossibility of exact T-state concentration, we build six- and eight-copy protocols producing an exact CCZ state, with six copies being minimal. Their success probabilities are governed by the linearized order-three stabilizer Rényi entropy M3lin. We show that this connection is structural: for up to nine input copies, M3lin fully determines the success probability of every universal Clifford-invariant stabilizer protocol. Remarkably, this characterization persists asymptotically: our constructions achieve optimal rates among universal single-output protocols and remain optimal up to logarithmic factors among arbitrary stabilizer protocols. As a corollary, we show that any unknown pure non-stabilizer state suffices for universal quantum computation via probabilistic CCZ-state injection. Together, these results identify the stabilizer Rényi entropy as a fundamental operational quantity in magic state distillation.
Non-local magic quantifies the non-stabilizerness of a bipartite quantum state that cannot be removed by local unitary transformations. Despite its natural definition, its evaluation generally requires a difficult optimization over local unitaries. Here, we show that for the log-stabilizer fidelity this optimization admits an exact closed-form analytic solution depending only on the Schmidt spectrum. We then introduce the magic of purification, defined as the minimum pure-state magic over all purifications of a mixed state, and show that it naturally induces a resource theory whose free states are normalized stabilizer-code projectors. For the log-stabilizer fidelity, the magic of purification admits a distance-based formulation in terms of the Uhlmann fidelity. Remarkably, we prove that non-local magic coincides with the minimum magic of purification along the unitary orbit of the reduced density operator. Our results provide both an efficient analytical characterization and a mixed-state resource-theoretic interpretation of non-local magic.
Nonstabilizerness is a critical resource for quantum advantage, but evaluating it, especially for mixed states, requires superexponentially many samples in system size, making the problem NP-hard. While symmetries are known to reduce this complexity, it is unclear whether they also restrict the amount of magic. In this work, we provide an explicit example of such a symmetry by proving that the Robustness of Magic (RoM) for N-qubit X-states is at most 3. Leveraging this symmetry constraint, we introduce a computationally efficient method to lower-bound the RoM of arbitrary many-body states, demonstrating its utility on the ground states of a spin-1/2 Hamiltonian with system sizes well beyond the reach of exact evaluation. Furthermore, for Hamiltonians whose equilibrium states are X-states, we analytically derive the critical temperature at which magic emerges. Our work shows why certain symmetries constrain magic while others do not, provides a scalable lower-bounding method, and identifies a nontrivial regime where many-body nonstabilizerness is analytically solvable.
We prove that, for an n-qubit system of dimension d=2n, every state satisfying Tr(ρ2)≤1/(d−a∗), with a∗=0.458327⋯, lies inside the stabilizer polytope and is therefore magic-free. Combining this result with general geometric properties of high-dimensional polytopes, we establish quantitative estimates for the Hilbert--Schmidt inradius and volume radius of the stabilizer polytope, and use them to characterize the typicality of magic in random induced states obtained by tracing out a k-dimensional subsystem from a d×k-dimensional Haar-random pure state. We prove a sharp phase transition in the probability of such states having magic, whose transition dimension k⋆ is bounded between Ω(d2/log2d) and O(d2). We further prove that the number of facets of the stabilizer polytope lies between exp[Ω(d2/log2d)] and exp[O(d2log2d)] employing a result of Bourgain and Milman in convex geometry, substantially improving upon the previous quasipolynomial lower bound and implying that doubly-exponentially many linear inequalities in the number of qubits are required for an exact description of the magic-free region. Overall, our results reveal the near-extremal geometry of the stabilizer polytope and provide a quantitative foundation for understanding the typicality, robustness, and detectability of magic.