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 $\sqrt{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.
AI Summary
The paper asks when symmetry both simplifies magic quantification and bounds the available resource. It studies $N$-qubit X-states, whose density matrices have support only on the diagonal and antidiagonal. The imposed symmetry is commutation with every adjacent parity check $Z_iZ_{i+1}$, rather than a single global parity.
Each joint eigenspace carries one effective qubit spanned by complementary computational-basis strings. For sector populations $p_x$ and subnormalized logical Bloch vectors $\mathbf a_x$, the exact robustness of magic is $\mathcal R(\rho)=\sum_x\max\{p_x,\|\mathbf a_x\|_1\}$. Consequently, $\mathcal R(\rho)\leq\sqrt3$, independently of $N$. Matching signed stabilizer decompositions and feasible dual witnesses establish the formula; a Clifford decoder identifies the state as a classically flagged ensemble of single-qubit states.
An even-weight $Z$-Pauli twirl maps arbitrary states into this family without increasing robustness, providing a lower bound, optionally strengthened by Clifford preprocessing. Ground-state calculations for the transverse-field Ising model demonstrate certification through $N=15$. For symmetry-preserving Gibbs states, magic requires full-support transverse interactions: any $k$-local Hamiltonian with $k<N$ is diagonal and produces no magic. The thermal onset is derived analytically from each logical Bloch vector crossing the stabilizer octahedron.
Evaluation remains exponential in qubit number, though linear in the X-state description. The twirl certificate cannot exceed $\sqrt3$ and need not capture total magic; larger-system Clifford choices use randomized searches rather than exhaustive optimization. Constant robustness alone does not guarantee efficient simulation without efficient decomposition sampling and simulation of subsequent operations.
Little sign of AI-generated textStrong assumptionsOverclaims
Error found: The abstract incorrectly presents the superexponential number of stabilizer projectors in the robustness optimization as a superexponential sampling requirement.
The abstract's computational-efficiency claim needs qualification because direct evaluation of the proposed lower bound involves 2^(N−1) sectors and is linear in the explicit state description, not polynomial in qubit number.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper asks when symmetry both simplifies magic quantification and bounds the available resource. It studies N-qubit X-states, whose density matrices have support only on the diagonal and antidiagonal. The imposed symmetry is commutation with every adjacent parity check ZiZi+1, rather than a single global parity.
Each joint eigenspace carries one effective qubit spanned by complementary computational-basis strings. For sector populations px and subnormalized logical Bloch vectors ax, the exact robustness of magic is R(ρ)=∑xmax{px,∥ax∥1}. Consequently, R(ρ)≤3, independently of N. Matching signed stabilizer decompositions and feasible dual witnesses establish the formula; a Clifford decoder identifies the state as a classically flagged ensemble of single-qubit states.
An even-weight Z-Pauli twirl maps arbitrary states into this family without increasing robustness, providing a lower bound, optionally strengthened by Clifford preprocessing. Ground-state calculations for the transverse-field Ising model demonstrate certification through N=15. For symmetry-preserving Gibbs states, magic requires full-support transverse interactions: any k-local Hamiltonian with k<N is diagonal and produces no magic. The thermal onset is derived analytically from each logical Bloch vector crossing the stabilizer octahedron.
Evaluation remains exponential in qubit number, though linear in the X-state description. The twirl certificate cannot exceed 3 and need not capture total magic; larger-system Clifford choices use randomized searches rather than exhaustive optimization. Constant robustness alone does not guarantee efficient simulation without efficient decomposition sampling and simulation of subsequent operations.
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.
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.
Magic (nonstabilizerness) is a necessary but "expensive" kind of "fuel" to drive universal fault-tolerant quantum computation.To properly study and characterize the origin of quantum "complexity" in computation as well as physics, it is crucial to develop a rigorous understanding of the quantification of magic.Previous studies of magic mostly focused on small systems and largely relied on the discrete Wigner formalism (which is only well behaved in odd prime power dimensions).Here we present an initiatory study of the magic of genuinely many-body quantum states that may be strongly entangled, with focus on the important case of many qubits, at a quantitative level.We first address the basic question of how "magical" a many-body state can be, and show that the maximum magic of an n-qubit state is essentially n, simultaneously for a range of "good" magic measures.As a corollary, the resource theory of magic has asymptotic golden currency states.We then show that, in fact, almost all n-qubit pure states have magic of nearly n.In the quest for explicit, scalable cases of highly entangled states whose magic can be understood, we connect the magic of hypergraph states with the second-order nonlinearity of their underlying Boolean functions.Next, we go on and investigate many-body magic in practical and physical contexts.We first consider a variant of measurement-based quantum computation where the client is restricted to Pauli measurements, in which magic is a necessary feature of the initial "resource" state.We show that n-qubit states with nearly n magic, or indeed almost all states, cannot supply nontrivial speedups over classical computers.We then present an example of analyzing the magic of "natural" condensed matter systems of physical interest.We apply the Boolean function techniques to derive explicit bounds on the magic of certain representative two-dimensional symmetry-protected topological states, and comment on possible further connections between magic and the quantum complexity of phases of matter.
Entanglement and magic are fundamental resources that capture the complexity of quantum many-body systems. Non-local magic isolates the irreducible nonstabilizerness intrinsically tied to entanglement. However, evaluating this quantity generally requires a prohibitive minimization over the full Hilbert space, making it computationally inaccessible beyond a few qubits. Here, we overcome this bottleneck by establishing a closed-form expression for the non-local stabilizer entropies of fermionic Gaussian states over local Gaussian unitaries, which we prove at Rényi index α=2 for arbitrary subsystem size, and which can be evaluated in polynomial time directly from the eigenvalues of the reduced Majorana covariance matrix. We apply this framework to characterize fermionic non-local magic across diverse physical regimes: we derive an exact Page-like curve for typical random states, reveal logarithmic scaling at the quantum critical point of the XY model, and establish a quasiparticle picture for magic generation during out-of-equilibrium quantum quenches. Crucially, because our result relies solely on two-point correlation functions, it provides a scalable route for the experimental estimation of fermionic non-local magic in large-scale quantum processors via fermionic shadow tomography.
Abstract Quantum many-body systems have been extensively studied from the perspective of quantum technology, and conversely, critical phenomena in such systems have been characterized by operationally relevant resources like entanglement. In this paper, we investigate robustness of magic (RoM), the resource in magic state injection based quantum computation schemes, in the context of the transverse field anisotropic XY model. We show that the the factorizable ground state in the symmetry broken configuration is composed of an enormous number of highly magical H states. We find the existence of a point very near the quantum critical point where magic contained explicitly in the correlation between two distant qubits attains a sharp maxima. Unlike bipartite entanglement, this persists over very long distances, capturing the presence of long range correlation near the phase transition. We derive scaling laws and extract corresponding exponents around criticality. Finally, we study the effect of temperature on two-qubit RoM and show that it reveals a crossover between dominance of quantum and thermal fluctuations.
Magic, or nonstabilizerness, characterizes the deviation of a quantum state from the set of stabilizer states, playing a fundamental role in quantum state complexity and universal fault-tolerant quantum computing. However, analytical and numerical characterizations of magic are very challenging, especially for multi-qubit systems, even with a moderate qubit number. Here, we systemically and analytically investigate the magic resource of archetypal multipartite quantum states—quantum hypergraph states, which can be generated by multi-qubit controlled-phase gates encoded by hypergraphs. We first derive the magic formula in terms of the stabilizer Rényi- α entropies for general quantum hypergraph states. If the average degree of the corresponding hypergraph is constant, we show that magic cannot reach the maximal value, i.e., the number of qubits n . Then, we investigate the statistical behaviors of random hypergraph states' magic and prove a concentration result, indicating that random hypergraph states typically reach the maximum magic. This also suggests an efficient way to generate maximal magic states with random diagonal circuits. Finally, we study hypergraph states with permutation symmetry, such as 3 -complete hypergraph states, where any three vertices are connected by a hyperedge. Counterintuitively, such states can only possess constant or even exponentially small magic for α≥2 . Our study advances the understanding of multipartite quantum magic and could lead to applications in quantum computing and quantum many-body physics.