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:2204.10061 · PRX Quantum

Scalable Measures of Magic Resource for Quantum Computers

Tobias Haug, M. S. Kim

Published Jan 3, 2023• 121 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/prxquantum.4.010301

Related papers

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

Algorithm for estimating α -stabilizer Rényi entropies via purity

Benjamin Stratton

Nonstabilizerness, or “magic,” is a resource for universal quantum computation in most fault-tolerant architectures; access to states with nonstabilizerness allows for nonclassically simulable quantum computation to be performed. Quantifying this resource for unknown states is therefore essential to assessing their utility in quantum computation. The stabilizer Rényi entropies have emerged as a leading tool for achieving this, having already enabled one efficient algorithm for measuring nonstabilizerness. In addition, the stabilizer Rényi entropies have proven useful in developing connections between nonstabilizerness and other quantum phenomena. In this work, we introduce an alternative algorithm for measuring the stabilizer Rényi entropies of an unknown quantum state. First, we show the existence of a state, produced from the action of a channel on α copies of some state ρ , that encodes the α -stabilizer Rényi entropy of ρ into its purity. We detail several methods of applying this channel, and then, by employing existing purity-measuring algorithms, provide an algorithm for measuring the α -stabilizer Rényi entropies for all integers α > 1 . This algorithm is benchmarked for qubits and the resource requirements compared to other known algorithms. Finally, a nonstabilizerness-entanglement relationship is shown to exist in the algorithm, demonstrating a relationship between the two resources, before an instance of resource hiding is found.

arXiv:2507.02540•Physical Review A•Jan 23, 2026•4 citations

Efficient witnessing and testing of magic in mixed quantum states

Tobias Haug, Poetri Sonya Tarabunga

Nonstabilizerness, or ‘magic’, is a crucial resource for quantum computation, but quantifying the magic of mixed states has been a notoriously difficult task. We introduce efficient magic witnesses based on stabilizer Rényi entropy that both robustly indicate magic and quantitatively estimate magic monotones. Building on these witnesses, we design testing algorithms that distinguish high- and low-magic states under entropy constraints and apply them to certify the number of noisy T-gates for a broad class of noise models. Using the IonQ quantum computer, we experimentally verify magic in noisy random circuits and find that magic remains robust, persisting even under depolarizing noise with probability exponentially close to one. Our witnesses are efficiently computable for matrix product states, showing that subsystems of many-body states can host extensive magic even when the system is entangled. Finally, we show that mimicking high-magic states with minimal magic requires an extensive amount of entropy, implying that entropy is a necessary cryptographic resource for hiding magic from eavesdroppers. Our results provide practical tools for characterizing the complexity of noisy quantum systems.

arXiv:2504.18098•npj Quantum Information•Feb 3, 2026•38 citations

Testing nonstabilizerness only with stabilizer states

Hyukjoon Kwon

The stabilizer formalism plays a central role in quantum information processing and quantum computing. Since stabilizer states and operations can be efficiently simulated classically and fault-tolerantly implemented in quantum error-correcting codes, quantum states and operations beyond the stabilizer framework, characterized by nonstabilizerness or magic, naturally emerge as resources for quantum computation. Here, we demonstrate that a quantum-information task involving only stabilizer states can reveal a fundamental limitation of stabilizer operations. Specifically, we construct a set of mutually orthogonal stabilizer states that cannot be perfectly distinguished using stabilizer operations and extend this construction to an arbitrary number of qubits. Our results provide an efficient test of nonstabilizerness without requiring the direct use of resourceful states or operations nor relying on computational-hardness assumptions. This nonstabilizerness test could serve as a resource-efficient benchmark for fault-tolerant quantum computers powered by magic-state injection, by providing quantitative bounds on the robustness of magic. More fundamentally, the resulting asymmetry between the preparation and discrimination of free states parallels "nonlocality without entanglement" in entanglement theory, revealing an unexpected connection between these two distinct quantum resource theories.

arXiv:2509.25790•Sep 30, 2025•7 citations

Magic transition in measurement-only circuits

Poetri Sonya Tarabunga, Emanuele Tirrito

Magic, or nonstabilizerness, quantifies the distance of a quantum state from stabilizer states and serves as a resource for quantum computational advantage. Here, we investigate magic transitions in measurement-only quantum circuits comprising competing Clifford and non-Clifford measurements. Remarkably, this circuit can be mapped onto a classical model, enabling efficient large-scale numerical simulations and exact characterization of magic using measures that are additive for tensor products of single-qubit states. We identify a magic transition between two phases exhibiting extensive magic, separated by a critical point where mutual magic displays scaling analogous to entanglement entropy. Additionally, these distinct phases can be distinguished by topological magic. In contrast, with a vanishing rate of non-Clifford measurements, the system exhibits saturation of magic. Our results clarify the nature of magic and its linear combinations in quantum circuits utilizing genuine magic measures, thereby advancing our understanding of quantum complexity in monitored quantum systems.

arXiv:2407.15939•npj Quantum Information•Oct 21, 2025•34 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•PRX Quantum•Feb 24, 2026•11 citations
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.
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.
Nonstabilizerness, or “magic,” is a resource for universal quantum computation in most fault-tolerant architectures; access to states with nonstabilizerness allows for nonclassically simulable quantum computation to be performed. Quantifying this resource for unknown states is therefore essential to assessing their utility in quantum computation. The stabilizer Rényi entropies have emerged as a leading tool for achieving this, having already enabled one efficient algorithm for measuring nonstabilizerness. In addition, the stabilizer Rényi entropies have proven useful in developing connections between nonstabilizerness and other quantum phenomena. In this work, we introduce an alternative algorithm for measuring the stabilizer Rényi entropies of an unknown quantum state. First, we show the existence of a state, produced from the action of a channel on α copies of some state ρ , that encodes the α -stabilizer Rényi entropy of ρ into its purity. We detail several methods of applying this channel, and then, by employing existing purity-measuring algorithms, provide an algorithm for measuring the α -stabilizer Rényi entropies for all integers α > 1 . This algorithm is benchmarked for qubits and the resource requirements compared to other known algorithms. Finally, a nonstabilizerness-entanglement relationship is shown to exist in the algorithm, demonstrating a relationship between the two resources, before an instance of resource hiding is found.
Nonstabilizerness, or ‘magic’, is a crucial resource for quantum computation, but quantifying the magic of mixed states has been a notoriously difficult task. We introduce efficient magic witnesses based on stabilizer Rényi entropy that both robustly indicate magic and quantitatively estimate magic monotones. Building on these witnesses, we design testing algorithms that distinguish high- and low-magic states under entropy constraints and apply them to certify the number of noisy T-gates for a broad class of noise models. Using the IonQ quantum computer, we experimentally verify magic in noisy random circuits and find that magic remains robust, persisting even under depolarizing noise with probability exponentially close to one. Our witnesses are efficiently computable for matrix product states, showing that subsystems of many-body states can host extensive magic even when the system is entangled. Finally, we show that mimicking high-magic states with minimal magic requires an extensive amount of entropy, implying that entropy is a necessary cryptographic resource for hiding magic from eavesdroppers. Our results provide practical tools for characterizing the complexity of noisy quantum systems.
The stabilizer formalism plays a central role in quantum information processing and quantum computing. Since stabilizer states and operations can be efficiently simulated classically and fault-tolerantly implemented in quantum error-correcting codes, quantum states and operations beyond the stabilizer framework, characterized by nonstabilizerness or magic, naturally emerge as resources for quantum computation. Here, we demonstrate that a quantum-information task involving only stabilizer states can reveal a fundamental limitation of stabilizer operations. Specifically, we construct a set of mutually orthogonal stabilizer states that cannot be perfectly distinguished using stabilizer operations and extend this construction to an arbitrary number of qubits. Our results provide an efficient test of nonstabilizerness without requiring the direct use of resourceful states or operations nor relying on computational-hardness assumptions. This nonstabilizerness test could serve as a resource-efficient benchmark for fault-tolerant quantum computers powered by magic-state injection, by providing quantitative bounds on the robustness of magic. More fundamentally, the resulting asymmetry between the preparation and discrimination of free states parallels "nonlocality without entanglement" in entanglement theory, revealing an unexpected connection between these two distinct quantum resource theories.
Magic, or nonstabilizerness, quantifies the distance of a quantum state from stabilizer states and serves as a resource for quantum computational advantage. Here, we investigate magic transitions in measurement-only quantum circuits comprising competing Clifford and non-Clifford measurements. Remarkably, this circuit can be mapped onto a classical model, enabling efficient large-scale numerical simulations and exact characterization of magic using measures that are additive for tensor products of single-qubit states. We identify a magic transition between two phases exhibiting extensive magic, separated by a critical point where mutual magic displays scaling analogous to entanglement entropy. Additionally, these distinct phases can be distinguished by topological magic. In contrast, with a vanishing rate of non-Clifford measurements, the system exhibits saturation of magic. Our results clarify the nature of magic and its linear combinations in quantum circuits utilizing genuine magic measures, thereby advancing our understanding of quantum complexity in monitored quantum systems.
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.