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:2311.01362 · Quantum

Handbook for Quantifying Robustness of Magic

Hiroki Hamaguchi, Kou Hamada, Nobuyuki Yoshioka

Published Sep 5, 2024• 36 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2024-09-05-1461

Related papers

Robustness of Magic and Symmetries of the Stabiliser Polytope

Markus Heinrich, David Gross

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.

arXiv:1807.10296•Quantum•Apr 8, 2019•147 citations

Efficient Quantum Algorithms for Stabilizer Entropies

Tobias Haug, Soovin Lee, M. S. Kim

Stabilizer entropies (SEs) are measures of nonstabilizerness or "magic" that quantify the degree to which a state is described by stabilizers. SEs are especially interesting due to their connections to scrambling, localization and property testing. However, applications have been limited so far as previously known measurement protocols for SEs scale exponentially with the number of qubits. Here, we efficiently measure SEs for integer Rényi index n>1 via Bell measurements. The SE of N-qubit quantum states can be measured with O(n) copies and O(nN) classical computational time, where for even n we additionally require the complex conjugate of the state. We provide efficient bounds of various nonstabilizerness monotones that are intractable to compute beyond a few qubits. Using the IonQ quantum computer, we measure SEs of random Clifford circuits doped with non-Clifford gates and give bounds for the stabilizer fidelity, stabilizer extent, and robustness of magic. We provide efficient algorithms to measure Clifford-averaged 4n-point out-of-time-order correlators and multifractal flatness. With these measures we study the scrambling time of doped Clifford circuits and random Hamiltonian evolution depending on nonstabilizerness. Counterintuitively, random Hamiltonian evolution becomes less scrambled at long times, which we reveal with the multifractal flatness. Our results open up the exploration of nonstabilizerness with quantum computers.

arXiv:2305.19152•Physical Review Letters•Jun 13, 2024•103 citations

Robustness of Magic and the Directed Geometry of State Conversion

Satoshi Kanno, Yoshi-aki Shimada

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.

quant-pharXiv:2610.38401•Oct 29, 2026•0 citations

Scalable Measures of Magic Resource for Quantum Computers

Tobias Haug, M. S. Kim

Nonstabilizerness or magic resource characterizes the amount of non-Clifford operations needed to prepare quantum states.It is a crucial resource for quantum computing and a necessary condition for quantum advantage.However, quantifying magic resource beyond a few qubits has been a major challenge.Here, we introduce efficient measures of magic resource for pure quantum states with a sampling cost that is independent of the number of qubits.Our method uses Bell measurements over two copies of a state, which we implement in experiment together with a cost-free error-mitigation scheme.We show the transition of classically simulable stabilizer states into intractable quantum states on the IonQ quantum computer.For applications, we efficiently distinguish stabilizer and nonstabilizer states with low measurement cost even in the presence of experimental noise.Further, we propose a variational quantum algorithm to maximize our measure via the shift rule.Our algorithm can be free of barren plateaus even for highly expressible variational circuits.Finally, we experimentally demonstrate a Bell-measurement protocol for the stabilizer Rényi entropy as well as the Wallach-Meyer entanglement measure.Our results pave the way to understanding the nonclassical power of quantum computers, quantum simulators, and quantum many-body systems.

arXiv:2204.10061•PRX Quantum•Jan 3, 2023•121 citations

When Symmetry Suppresses Magic

A. de Oliveira Junior, Jake Xuereb, Rafael A. Macêdo +2 more

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.

quant-pharXiv:2609.38319•Oct 1, 2026•1 citation

Quantifying magic for multi-qubit operations

James R. Seddon, Earl T. Campbell

The development of a framework for quantifying ‘non-stabilizerness’ of quantum operations is motivated by the magic state model of fault-tolerant quantum computation and by the need to estimate classical simulation cost for noisy intermediate-scale quantum (NISQ) devices. The robustness of magic was recently proposed as a well-behaved magic monotone for multi-qubit states and quantifies the simulation overhead of circuits composed of Clifford + T gates, or circuits using other gates from the Clifford hierarchy. Here we present a general theory of the ‘non-stabilizerness’ of quantum operations rather than states, which are useful for classical simulation of more general circuits. We introduce two magic monotones, called channel robustness and magic capacity, which are well-defined for general n -qubit channels and treat all stabilizer-preserving CPTP maps as free operations. We present two complementary Monte Carlo-type classical simulation algorithms with sample complexity given by these quantities and provide examples of channels where the complexity of our algorithms is exponentially better than previously known simulators. We present additional techniques that ease the difficulty of calculating our monotones for special classes of channels.

arXiv:1901.03322•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jul 1, 2019•140 citations
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.
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.
Stabilizer entropies (SEs) are measures of nonstabilizerness or "magic" that quantify the degree to which a state is described by stabilizers. SEs are especially interesting due to their connections to scrambling, localization and property testing. However, applications have been limited so far as previously known measurement protocols for SEs scale exponentially with the number of qubits. Here, we efficiently measure SEs for integer Rényi index n>1 via Bell measurements. The SE of N-qubit quantum states can be measured with O(n) copies and O(nN) classical computational time, where for even n we additionally require the complex conjugate of the state. We provide efficient bounds of various nonstabilizerness monotones that are intractable to compute beyond a few qubits. Using the IonQ quantum computer, we measure SEs of random Clifford circuits doped with non-Clifford gates and give bounds for the stabilizer fidelity, stabilizer extent, and robustness of magic. We provide efficient algorithms to measure Clifford-averaged 4n-point out-of-time-order correlators and multifractal flatness. With these measures we study the scrambling time of doped Clifford circuits and random Hamiltonian evolution depending on nonstabilizerness. Counterintuitively, random Hamiltonian evolution becomes less scrambled at long times, which we reveal with the multifractal flatness. Our results open up the exploration of nonstabilizerness with quantum computers.
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 CFC_{\mathcal F}CF​ as the distance between a target state and the set of states freely reachable from a given input state. The quantity CFC_{\mathcal F}CF​ characterizes free convertibility and is related to the minimum stabilizer quasiprobability weight required to represent the conversion residual through the relation 1+2CF1+2C_{\mathcal F}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 resource characterizes the amount of non-Clifford operations needed to prepare quantum states.It is a crucial resource for quantum computing and a necessary condition for quantum advantage.However, quantifying magic resource beyond a few qubits has been a major challenge.Here, we introduce efficient measures of magic resource for pure quantum states with a sampling cost that is independent of the number of qubits.Our method uses Bell measurements over two copies of a state, which we implement in experiment together with a cost-free error-mitigation scheme.We show the transition of classically simulable stabilizer states into intractable quantum states on the IonQ quantum computer.For applications, we efficiently distinguish stabilizer and nonstabilizer states with low measurement cost even in the presence of experimental noise.Further, we propose a variational quantum algorithm to maximize our measure via the shift rule.Our algorithm can be free of barren plateaus even for highly expressible variational circuits.Finally, we experimentally demonstrate a Bell-measurement protocol for the stabilizer Rényi entropy as well as the Wallach-Meyer entanglement measure.Our results pave the way to understanding the nonclassical power of quantum computers, quantum simulators, and quantum many-body systems.
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.
The development of a framework for quantifying ‘non-stabilizerness’ of quantum operations is motivated by the magic state model of fault-tolerant quantum computation and by the need to estimate classical simulation cost for noisy intermediate-scale quantum (NISQ) devices. The robustness of magic was recently proposed as a well-behaved magic monotone for multi-qubit states and quantifies the simulation overhead of circuits composed of Clifford + T gates, or circuits using other gates from the Clifford hierarchy. Here we present a general theory of the ‘non-stabilizerness’ of quantum operations rather than states, which are useful for classical simulation of more general circuits. We introduce two magic monotones, called channel robustness and magic capacity, which are well-defined for general n -qubit channels and treat all stabilizer-preserving CPTP maps as free operations. We present two complementary Monte Carlo-type classical simulation algorithms with sample complexity given by these quantities and provide examples of channels where the complexity of our algorithms is exponentially better than previously known simulators. We present additional techniques that ease the difficulty of calculating our monotones for special classes of channels.