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

arXiv:2609.38319

When Symmetry Suppresses Magic

A. de Oliveira Junior, Jake Xuereb, Rafael A. Macêdo, Jonatan Bohr Brask, Rafael Chaves

quant-phSubmitted Sep 29, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
5 + 10 pages, 3 figures. Comments welcome

Related papers

Handbook for Quantifying Robustness of Magic

Hiroki Hamaguchi, Kou Hamada, Nobuyuki Yoshioka

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.

arXiv:2311.01362•Quantum•Sep 5, 2024•23 citations

Predicting Magic from Very Few Measurements

J. M. Varela, L. L. Keller, A. de Oliveira Junior +3 more

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 $m$ $n$-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 $\mathrm{P} = \mathrm{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.

quant-pharXiv:2602.18939•Feb 24, 2026•0 citations

Many-Body Quantum Magic

Zi-Wen Liu, Andreas Winter

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.

arXiv:2010.13817•PRX Quantum•May 12, 2022•169 citations

Non-Local Magic Resources for Fermionic Gaussian States

Daniele Iannotti, Beatrice Magni, Riccardo Cioli +2 more

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.

quant-pharXiv:2604.27049•May 1, 2026•0 citations

Characterization of an operational quantum resource in a critical many-body system

S Sarkar, C Mukhopadhyay, Abolfazl Bayat

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.

arXiv:1908.08058•New Journal of Physics•Jul 24, 2020•39 citations

Predicting Magic from Very Few Measurements

J. M. Varela, L. L. Keller, A. de Oliveira +3 more

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 set of m n -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.

PRX Quantum•Jul 31, 2026•0 citations
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\sqrt{3}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.
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 mmm nnn-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 mmm and polynomial in the number of qubits nnn. 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\mathrm{P} = \mathrm{NP}P=NP, no algorithm polynomial in mmm 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α=2α=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.
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 set of m n -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.