We prove that, for an $n$-qubit system of dimension $d=2^n$, every state satisfying $\operatorname{Tr}(ρ^2)\le 1/(d-a_\ast)$, with $a_\ast=0.458327\cdots$, 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\times k$-dimensional Haar-random pure state. We prove a sharp phase transition in the probability of such states having magic, whose transition dimension $k_\star$ is bounded between $Ω(d^2/\log^2d)$ and $\mathcal{O}(d^2)$. We further prove that the number of facets of the stabilizer polytope lies between $\exp[Ω(d^2/\log^2 d)]$ and $\exp[\mathcal{O}(d^2\log^2 d)]$, substantially improving upon the previous quasipolynomial lower bound and implying that any exact description of the magic-free region requires a doubly exponential number of linear inequalities in the number of qubits. Overall, our results show that the stabilizer polytope exhibits near-maximal geometric complexity allowed for a high-dimensional polytope with a certain number of vertices.
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)], substantially improving upon the previous quasipolynomial lower bound and implying that any exact description of the magic-free region requires a doubly exponential number of linear inequalities in the number of qubits. Overall, our results show that the stabilizer polytope exhibits near-maximal geometric complexity allowed for a high-dimensional polytope with a certain number of vertices.
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.
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.
We give a new algorithm for computing the robustness of magic-a measure of the utility of quantum states as a computational resource. Our work is motivated by the magic state model of fault-tolerant quantum computation. In this model, all unitaries belong to the Clifford group. Non-Clifford operations are effected by injecting non-stabiliser states, which are referred to as magic states in this context. The robustness of magic measures the complexity of simulating such a circuit using a classical Monte Carlo algorithm. It is closely related to the degree negativity that slows down Monte Carlo simulations through the infamous sign problem. Surprisingly, the robustness of magic is submultiplicative. This implies that the classical simulation overhead scales subexponentially with the number of injected magic states-better than a naive analysis would suggest. However, determining the robustness of n copies of a magic state is difficult, as its definition involves a convex optimisation problem in a 4(n)-dimensional space. In this paper, we make use of inherent symmetries to reduce the problem to n dimensions. The total run-time of our algorithm, while still exponential in n, is super-polynomially faster than previously published methods. We provide a computer implementation and give the robustness of up to 10 copies of the most commonly used magic states. Guided by the exact results, we find a finite hierarchy of approximate solutions where each level can be evaluated in polynomial time and yields rigorous upper bounds to the robustness. Technically, we use symmetries of the stabiliser polytope to connect the robustness of magic to the geometry of a low-dimensional convex polytope generated by certain signed quantum weight enumerators. As a by-product, we characterised the automorphism group of the stabiliser polytope, and, more generally, of projections onto complex projective 3-designs.
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 n2 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.
We give a new algorithm for computing the robustness of magic - a measure of the utility of quantum states as a computational resource. Our work is motivated by the magic state model of fault-tolerant quantum computation. In this model, all unitaries belong to the Clifford group. Non-Clifford operations are effected by injecting non-stabiliser states, which are referred to as magic states in this context. The robustness of magic measures the complexity of simulating such a circuit using a classical Monte Carlo algorithm. It is closely related to the degree negativity that slows down Monte Carlo simulations through the infamous sign problem . Surprisingly, the robustness of magic is sub - multiplicative. This implies that the classical simulation overhead scales subexponentially with the number of injected magic states - better than a naive analysis would suggest. However, determining the robustness of n copies of a magic state is difficult, as its definition involves a convex optimisation problem in a 4 n -dimensional space. In this paper, we make use of inherent symmetries to reduce the problem to n dimensions. The total run-time of our algorithm, while still exponential in n , is super-polynomially faster than previously published methods. We provide a computer implementation and give the robustness of up to 10 copies of the most commonly used magic states. Guided by the exact results, we find a finite hierarchy of approximate solutions where each level can be evaluated in polynomial time and yields rigorous upper bounds to the robustness. Technically, we use symmetries of the stabiliser polytope to connect the robustness of magic to the geometry of a low-dimensional convex polytope generated by certain signed quantum weight enumerators . As a by-product, we characterised the automorphism group of the stabiliser polytope, and, more generally, of projections onto complex projective 3-designs.
We prove that every pure state of stabilizer rank at most k has stabilizer extent at most 2O(klog(k+1)), and establish the analogous bound for the squared Clifford coefficient norm of Clifford-rank-k operators. This implies stabilizer fidelity at least 2−O(klog(k+1)), resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an Ω(n2/logn) lower bound for the approximate stabilizer rank of tensor powers of any non-stabilizer qubit state. The latter result generalizes the best-known lower bound for tensor powers of T-states (Mehraban-Tamasbi, STOC, 2024) to arbitrary non-stabilizer qubit states, including magic states.
As a consequence of the Clifford rank--norm inequality, we obtain an Ω(n2/logn) lower bound for exact representations of n-bit AND function by quadratic phases, improving the previous best-known linear bound. Further consequences rule out pseudorandom state and unitary ensembles with approximate stabilizer and Clifford rank O((logn)2/loglogn), respectively, a logn improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most k, with poly(n)2O(klog(k+1)) time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.