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:2601.00761

Exponentially Accelerated Sampling of Pauli Strings for Nonstabilizerness

Zhenyu Xiao, Shinsei Ryu

quant-phcond-mat.mes-hallcond-mat.stat-mechSubmitted Jan 2, 2026• Announced Jan 5, 2026• 0 citations
v1 · Jan 2, 2026v2 · Apr 19, 2026
arXivHTMLPDF

Abstract

Quantum magic, quantified by nonstabilizerness, measures departures from stabilizer structure and underlies potential quantum speedups. We introduce an efficient classical algorithm that exactly computes stabilizer Rényi entropies and stabilizer nullity for generic many-body wavefunctions of $N$ qubits. The method combines the fast Walsh-Hadamard transform with an exact partition of Pauli operators. It achieves an exponential speedup over direct approaches, reducing the average cost per sampled Pauli string from $O(2^N)$ to $O(N)$. Building on this framework, we further develop a Monte-Carlo estimator for stabilizer Rényi entropies together with a Clifford-based variance-reduction scheme that suppresses sampling fluctuations. We benchmark the accuracy and efficiency on ensembles of random magic states, and apply the method to random Clifford circuits with doped $T$ gates, comparing different doping architectures. Our approach applies to arbitrary quantum states and provides quantitative access to magic resources both encoded in highly entangled states and generated by long-time nonequilibrium dynamics.

Related papers

Exponentially Accelerated Sampling of Pauli Strings for Nonstabilizerness

Anonymous, Shinsei Ryu

Quantum magic, quantified by nonstabilizerness, measures departures from stabilizer structure and underlies potential quantum speedups. We introduce an efficient classical framework for computing stabilizer Rényi entropies and stabilizer nullity of generic N-qubit wave functions. The method combines the fast Walsh-Hadamard transform with an exact partition of Pauli operators, reducing the average cost per sampled Pauli string from O(2^{N}) to O(N). We further develop a Monte Carlo estimator with Clifford preconditioning and find that the required number of samples shows no visible growth with N in our benchmarks. Applying the method to T-doped random Clifford circuits, we identify the scrambling ratio η (Clifford gates per T gate) as the key parameter governing magic growth. Each T gate approaches its dilute-limit nonstabilizerness power with only modest Clifford scrambling. Our approach enables quantitative studies of magic in highly entangled states and long-time nonequilibrium dynamics.

Physical Review Letters•Jul 20, 2026•1 citation

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•72 citations

Computing quantum magic of state vectors

Piotr Sierant, Jofre Vallès-Muns, Artur Garcia-Saez

Non-stabilizerness, also known as ``magic,'' quantifies how far a quantum state departs from the stabilizer set. It is a central resource behind quantum advantage and a useful probe of the complexity of quantum many-body states. Yet standard magic quantifiers, such as the stabilizer Rényi entropy (SRE) for qubits and the mana for qutrits, are costly to evaluate numerically, with the computational complexity growing rapidly with the number $N$ of qudits. Here we introduce efficient, numerically exact algorithms that exploit the fast Hadamard transform to compute the SRE for qubits ($d=2$) and the mana for qutrits ($d=3$) for pure states given as state vectors. Our methods compute SRE and mana at cost $O(N d^{2N})$, providing an exponential improvement over the naive $O(d^{3N})$ scaling, with substantial parallelism and straightforward GPU acceleration. We further show how to combine the fast Hadamard transform with Monte Carlo sampling to estimate the SRE of state vectors, and we extend the approach to compute the mana of mixed states. All algorithms are implemented in the open-source Julia package HadaMAG ( https://github.com/bsc-quantic/HadaMAG.jl/ ), which provides a high-performance toolbox for computing SRE and mana with built-in support for multithreading, MPI-based distributed parallelism, and GPU acceleration. The package, together with the methods developed in this work, offers a practical route to large-scale numerical studies of magic in quantum many-body systems.

quant-pharXiv:2601.07824•Quantum•Jan 13, 2026•7 citations

Rise and fall of nonstabilizerness via random measurements

Annarita Scocco, Wai‐Keong Mok, Leandro Aolita +2 more

We investigate the dynamics of nonstabilizerness—also known as “magic”—in monitored quantum circuits composed of random Clifford unitaries and local measurements. For measurements in the computational basis, we derive an analytical model for dynamics of the stabilizer nullity, showing that it decays in quantized steps and requires exponentially many measurements to vanish, which reveals the strong protection through Clifford scrambling. On the other hand, for measurements performed in rotated non-Clifford bases, measurements can both create and destroy nonstabilizerness. Here, the dynamics leads to a steady state with nontrivial nonstabilizerness, independent of the initial state. We find that Haar-random states equilibrate in constant time, whereas stabilizer states exhibit linear-in-size relaxation time. While the stabilizer nullity is insensitive to the rotation angle, stabilizer Rényi entropies expose a richer structure in their dynamics. Our results uncover sharp distinctions between coarse and fine-grained nonstabilizerness diagnostics and demonstrate how measurements can both suppress and sustain quantum computational resources.

arXiv:2507.11619•Physical Review Research•Dec 23, 2025•4 citations

Probing quantum complexity via universal saturation of stabilizer entropies

Tobias Haug, Leandro Aolita, M. S. Kim

Nonstabilizerness or `magic' is a key resource for quantum computing and a necessary condition for quantum advantage. Non-Clifford operations turn stabilizer states into resourceful states, where the amount of nonstabilizerness is quantified by resource measures such as stabilizer Rényi entropies (SREs). Here, we show that SREs saturate their maximum value at a critical number of non-Clifford operations. Close to the critical point SREs show universal behavior. Remarkably, the derivative of the SRE crosses at the same point independent of the number of qubits and can be rescaled onto a single curve. We find that the critical point depends non-trivially on Rényi index α . For random Clifford circuits doped with T-gates, the critical T-gate density scales independently of α . In contrast, for random Hamiltonian evolution, the critical time scales linearly with qubit number for α > 1 , while it is a constant for α < 1 . This highlights that α -SREs reveal fundamentally different aspects of nonstabilizerness depending on α : α -SREs with α < 1 relate to Clifford simulation complexity, while α > 1 probe the distance to the closest stabilizer state and approximate state certification cost via Pauli measurements. As technical contributions, we observe that the Pauli spectrum of random evolution can be approximated by two highly concentrated peaks which allows us to compute its SRE. Further, we introduce a class of random evolution that can be expressed as random Clifford circuits and rotations, where we provide its exact SRE. Our results opens up new approaches to characterize the complexity of quantum systems.

arXiv:2406.04190•Quantum•Jul 21, 2025•32 citations

Magic Resources of the Heisenberg Picture

Neil Dowling, Pavel Kos, Xhek Turkeshi

We study a nonstabilizerness resource theory for operators, which is dual to that describing states. We identify that the stabilizer Rényi entropy analog in operator space is a good magic monotone satisfying the usual conditions while inheriting efficient computability properties and providing a tight lower bound to the minimum number of non-Clifford gates in a circuit. Operationally, this measure quantifies how well an operator can be approximated by one with only a few Pauli strings-analogous to how entanglement entropy relates to tensor-network truncation. A notable advantage of operator stabilizer entropies is their inherent locality, as captured by a Lieb-Robinson bound. This feature makes them particularly suited for studying local dynamical magic resource generation in many-body systems. We compute this quantity analytically in two distinct regimes. First, we show that under random evolution, operator magic typically reaches near-maximal value for all Rényi indices, and we evaluate the Page correction. Second, harnessing both dual unitarity and ZX graphical calculus, we solve the operator stabilizer entropy for interacting integrable XXZ circuit, finding that it quickly saturates to a constant value. Overall, this measure sheds light on the structural properties of many-body nonstabilizerness generation and can inspire Clifford-assisted tensor network methods.

arXiv:2408.16047•Physical Review Letters•Jul 7, 2025•25 citations
Quantum magic, quantified by nonstabilizerness, measures departures from stabilizer structure and underlies potential quantum speedups. We introduce an efficient classical algorithm that exactly computes stabilizer Rényi entropies and stabilizer nullity for generic many-body wavefunctions of NNN qubits. The method combines the fast Walsh-Hadamard transform with an exact partition of Pauli operators. It achieves an exponential speedup over direct approaches, reducing the average cost per sampled Pauli string from O(2N)O(2^N)O(2N) to O(N)O(N)O(N). Building on this framework, we further develop a Monte-Carlo estimator for stabilizer Rényi entropies together with a Clifford-based variance-reduction scheme that suppresses sampling fluctuations. We benchmark the accuracy and efficiency on ensembles of random magic states, and apply the method to random Clifford circuits with doped TTT gates, comparing different doping architectures. Our approach applies to arbitrary quantum states and provides quantitative access to magic resources both encoded in highly entangled states and generated by long-time nonequilibrium dynamics.
Quantum magic, quantified by nonstabilizerness, measures departures from stabilizer structure and underlies potential quantum speedups. We introduce an efficient classical framework for computing stabilizer Rényi entropies and stabilizer nullity of generic N-qubit wave functions. The method combines the fast Walsh-Hadamard transform with an exact partition of Pauli operators, reducing the average cost per sampled Pauli string from O(2^{N}) to O(N). We further develop a Monte Carlo estimator with Clifford preconditioning and find that the required number of samples shows no visible growth with N in our benchmarks. Applying the method to T-doped random Clifford circuits, we identify the scrambling ratio η (Clifford gates per T gate) as the key parameter governing magic growth. Each T gate approaches its dilute-limit nonstabilizerness power with only modest Clifford scrambling. Our approach enables quantitative studies of magic in highly entangled states and long-time nonequilibrium dynamics.
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.
Non-stabilizerness, also known as ``magic,'' quantifies how far a quantum state departs from the stabilizer set. It is a central resource behind quantum advantage and a useful probe of the complexity of quantum many-body states. Yet standard magic quantifiers, such as the stabilizer Rényi entropy (SRE) for qubits and the mana for qutrits, are costly to evaluate numerically, with the computational complexity growing rapidly with the number NNN of qudits. Here we introduce efficient, numerically exact algorithms that exploit the fast Hadamard transform to compute the SRE for qubits (d=2d=2d=2) and the mana for qutrits (d=3d=3d=3) for pure states given as state vectors. Our methods compute SRE and mana at cost O(Nd2N)O(N d^{2N})O(Nd2N), providing an exponential improvement over the naive O(d3N)O(d^{3N})O(d3N) scaling, with substantial parallelism and straightforward GPU acceleration. We further show how to combine the fast Hadamard transform with Monte Carlo sampling to estimate the SRE of state vectors, and we extend the approach to compute the mana of mixed states. All algorithms are implemented in the open-source Julia package HadaMAG ( https://github.com/bsc-quantic/HadaMAG.jl/ ), which provides a high-performance toolbox for computing SRE and mana with built-in support for multithreading, MPI-based distributed parallelism, and GPU acceleration. The package, together with the methods developed in this work, offers a practical route to large-scale numerical studies of magic in quantum many-body systems.
We investigate the dynamics of nonstabilizerness—also known as “magic”—in monitored quantum circuits composed of random Clifford unitaries and local measurements. For measurements in the computational basis, we derive an analytical model for dynamics of the stabilizer nullity, showing that it decays in quantized steps and requires exponentially many measurements to vanish, which reveals the strong protection through Clifford scrambling. On the other hand, for measurements performed in rotated non-Clifford bases, measurements can both create and destroy nonstabilizerness. Here, the dynamics leads to a steady state with nontrivial nonstabilizerness, independent of the initial state. We find that Haar-random states equilibrate in constant time, whereas stabilizer states exhibit linear-in-size relaxation time. While the stabilizer nullity is insensitive to the rotation angle, stabilizer Rényi entropies expose a richer structure in their dynamics. Our results uncover sharp distinctions between coarse and fine-grained nonstabilizerness diagnostics and demonstrate how measurements can both suppress and sustain quantum computational resources.
Nonstabilizerness or `magic' is a key resource for quantum computing and a necessary condition for quantum advantage. Non-Clifford operations turn stabilizer states into resourceful states, where the amount of nonstabilizerness is quantified by resource measures such as stabilizer Rényi entropies (SREs). Here, we show that SREs saturate their maximum value at a critical number of non-Clifford operations. Close to the critical point SREs show universal behavior. Remarkably, the derivative of the SRE crosses at the same point independent of the number of qubits and can be rescaled onto a single curve. We find that the critical point depends non-trivially on Rényi index α . For random Clifford circuits doped with T-gates, the critical T-gate density scales independently of α . In contrast, for random Hamiltonian evolution, the critical time scales linearly with qubit number for α > 1 , while it is a constant for α < 1 . This highlights that α -SREs reveal fundamentally different aspects of nonstabilizerness depending on α : α -SREs with α < 1 relate to Clifford simulation complexity, while α > 1 probe the distance to the closest stabilizer state and approximate state certification cost via Pauli measurements. As technical contributions, we observe that the Pauli spectrum of random evolution can be approximated by two highly concentrated peaks which allows us to compute its SRE. Further, we introduce a class of random evolution that can be expressed as random Clifford circuits and rotations, where we provide its exact SRE. Our results opens up new approaches to characterize the complexity of quantum systems.
We study a nonstabilizerness resource theory for operators, which is dual to that describing states. We identify that the stabilizer Rényi entropy analog in operator space is a good magic monotone satisfying the usual conditions while inheriting efficient computability properties and providing a tight lower bound to the minimum number of non-Clifford gates in a circuit. Operationally, this measure quantifies how well an operator can be approximated by one with only a few Pauli strings-analogous to how entanglement entropy relates to tensor-network truncation. A notable advantage of operator stabilizer entropies is their inherent locality, as captured by a Lieb-Robinson bound. This feature makes them particularly suited for studying local dynamical magic resource generation in many-body systems. We compute this quantity analytically in two distinct regimes. First, we show that under random evolution, operator magic typically reaches near-maximal value for all Rényi indices, and we evaluate the Page correction. Second, harnessing both dual unitarity and ZX graphical calculus, we solve the operator stabilizer entropy for interacting integrable XXZ circuit, finding that it quickly saturates to a constant value. Overall, this measure sheds light on the structural properties of many-body nonstabilizerness generation and can inspire Clifford-assisted tensor network methods.