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.07824 · Quantum

Computing quantum magic of state vectors

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

quant-phcond-mat.dis-nncond-mat.stat-mechSubmitted Jan 12, 2026• Announced Jan 13, 2026• 17 citations• Revised Apr 6, 2026 (v3)
v1 · Jan 12, 2026v2 · Jan 13, 2026v3 · Apr 6, 2026
arXivHTMLPDF

Abstract

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.

Journal reference
Quantum 10, 2059 (2026)
DOI
10.22331/q-2026-04-10-2059
Comments
25 pages, 1 figure. Comments welcome!

Related papers

A fast and exact approach for stabilizer Rényi entropy via the XOR-FWHT algorithm

Xuyang Huang, Han-Ze Li, Ching Hua Lee +1 more

Quantum advantage is widely understood to rely on key quantum resources beyond entanglement, among which nonstabilizerness (quantum ``magic'') plays a central role in enabling universal quantum computation. However, the exact evaluation of the second-order stabilizer Rényi entropy for generic many-body quantum states remains computationally challenging, with brute-force methods scaling as $\mathcal O(8^N)$ for an $N$-qubit state. Here we develop a deterministic and exact algorithm that reduces this cost to $\mathcal{O}(N4^N)$ while retaining natural parallelism. This advance enables high-precision exact calculations for generic state vectors at medium system sizes, and provides a practical tool for investigating the scaling, phase structure, and nonequilibrium dynamics of quantum magic in many-body systems.

quant-pharXiv:2512.24685•Physical Review Research•Jan 1, 2026•32 citations

Exponentially Accelerated Sampling of Pauli Strings for Nonstabilizerness

Zhenyu Xiao, 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 wavefunctions. The method combines the fast Walsh-Hadamard transform with an exact partition of Pauli operators, reducing the average cost per sampled Pauli string from $\mathcal{O}(2^N)$ to $\mathcal{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.

quant-pharXiv:2601.00761•Physical Review Letters•Jan 5, 2026•19 citations

Efficient mutual magic and magic capacity with matrix product states

Poetri Sonya Tarabunga, Tobias Haug

Stabilizer Rényi entropies (SREs) probe the non-stabilizerness (or “magic”) of many-body systems and quantum computers. Here, we introduce the mutual von-Neumann SRE and magic capacity, which can be efficiently computed in time O(N\chi^3) O ( N χ 3 ) for matrix product states (MPSs) of bond dimension \chi χ . We find that mutual SRE characterizes the critical point of ground states of the transverse-field Ising model, independently of the chosen local basis. Then, we relate the magic capacity to the anti-flatness of the Pauli spectrum, which quantifies the complexity of computing SREs. The magic capacity characterizes transitions in the ground state of the Heisenberg and Ising model, randomness of Clifford+T circuits, and distinguishes typical and atypical states. Finally, we make progress on numerical techniques: we design two improved Monte-Carlo algorithms to compute the mutual 2 2 -SRE, overcoming limitations of previous approaches based on local update. We also give improved statevector simulation methods for Bell sampling and SREs with O(8^{N/2}) O ( 8 N / 2 ) time and O(2^N) O ( 2 N ) memory, which we demonstrate for 24 24 qubits. Our work uncovers improved approaches to study the complexity of quantum many-body systems.

arXiv:2504.07230•SciPost Physics•Oct 6, 2025•38 citations

Stabilizer Rényi entropy of 3-uniform hypergraph states

Daichi Kagamihara, Shunji Tsuchiya

Nonstabilizerness, also known as magic, plays a central role in universal quantum computation. Hypergraph states are nonstabilizer generalizations of graph states and constitute a key class of quantum states in various areas of quantum physics, such as the demonstration of quantum advantage, measurement-based quantum computation, and the study of topological phases. In this work, we investigate nonstabilizerness of 3-uniform hypergraph states, which are solely generated by controlled-controlled-Z gates, in terms of the stabilizer Rényi entropy (SRE). We find that the SRE of 3-uniform hypergraph states can be expressed using the matrix rank, which reduces computational cost from $\mathcal{O}(2^{3N})$ to $\mathcal{O}(N^3 2^{N})$ for $N$-qubit states. Based on this result, we exactly evaluate SREs of one-dimensional hypergraph states. We also present numerical results of SREs of several large-scale 3-uniform hypergraph states. Our results would contribute to an understanding of the role of nonstabilizerness in a wide range of physical settings where hypergraph states are employed.

quant-pharXiv:2602.23687•Mar 2, 2026•0 citations

Quantifying non-stabilizerness via information scrambling

Arash Ahmadi, Eliška Greplová

The advent of quantum technologies brought forward much attention to the theoretical characterization of the computational resources they provide. A method to quantify quantum resources is to use a class of functions called magic monotones and stabilizer entropies, which are, however, notoriously hard and impractical to evaluate for large system sizes. In recent studies, a fundamental connection between information scrambling, the magic monotone mana and 2-Renyi stabilizer entropy was established. This connection simplified magic monotone calculation, but this class of methods still suffers from exponential scaling with respect to the number of qubits. In this work, we establish a way to sample an out-of-time-order correlator that approximates magic monotones and 2-Renyi stabilizer entropy. We numerically show the relation of these sampled correlators to different non-stabilizerness measures for both qubit and qutrit systems and provide an analytical relation to 2-Renyi stabilizer entropy. Furthermore, we put forward and simulate a protocol to measure the monotonic behaviour of magic for the time evolution of local Hamiltonians.

arXiv:2204.11236•SciPost Physics•Feb 8, 2024•34 citations

Magic in Grover's Algorithm and the Role of Oracle Synthesis

Alessio Paviglianiti, Vincenzo Savona

Grover's algorithm is a textbook example of quantum advantage, providing a quadratic query speedup over classical methods for unstructured search. In this Letter, we characterize the non-stabilizerness, or magic, developed throughout Grover's protocol, quantifying quantum complexity with respect to the efficiently simulable stabilizer states. First, we compute the compilation-independent magic at the end of each Grover iteration, deriving an analytic prediction for the stabilizer Rényi entropy and proving that it remains intensive as the system size grows. We then investigate the magic overhead due to decomposing the circuit into elementary gates. When the solution to the search problem is known, we show that an efficient decomposition exists that keeps magic bounded despite using an extensive number of Toffoli gates. In contrast, agnostic implementations are expected to generate volume-law non-stabilizerness, as we confirm for the 3-SAT problem, which rules out efficient simulation by stabilizer-based methods in practically relevant cases. Our findings clarify the growth of magic in Grover's algorithm and the role of solution-awareness in its circuit compilation.

quant-pharXiv:2610.37772•Oct 29, 2026•0 citations
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.
Quantum advantage is widely understood to rely on key quantum resources beyond entanglement, among which nonstabilizerness (quantum ``magic'') plays a central role in enabling universal quantum computation. However, the exact evaluation of the second-order stabilizer Rényi entropy for generic many-body quantum states remains computationally challenging, with brute-force methods scaling as O(8N)\mathcal O(8^N)O(8N) for an NNN-qubit state. Here we develop a deterministic and exact algorithm that reduces this cost to O(N4N)\mathcal{O}(N4^N)O(N4N) while retaining natural parallelism. This advance enables high-precision exact calculations for generic state vectors at medium system sizes, and provides a practical tool for investigating the scaling, phase structure, and nonequilibrium dynamics of quantum magic in many-body systems.
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 NNN-qubit wavefunctions. 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(2N)\mathcal{O}(2^N)O(2N) to O(N)\mathcal{O}(N)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 NNN in our benchmarks. Applying the method to TTT-doped random Clifford circuits, we identify the scrambling ratio ηηη (Clifford gates per TTT gate) as the key parameter governing magic growth. Each TTT 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 Rényi entropies (SREs) probe the non-stabilizerness (or “magic”) of many-body systems and quantum computers. Here, we introduce the mutual von-Neumann SRE and magic capacity, which can be efficiently computed in time O(N\chi^3) O ( N χ 3 ) for matrix product states (MPSs) of bond dimension \chi χ . We find that mutual SRE characterizes the critical point of ground states of the transverse-field Ising model, independently of the chosen local basis. Then, we relate the magic capacity to the anti-flatness of the Pauli spectrum, which quantifies the complexity of computing SREs. The magic capacity characterizes transitions in the ground state of the Heisenberg and Ising model, randomness of Clifford+T circuits, and distinguishes typical and atypical states. Finally, we make progress on numerical techniques: we design two improved Monte-Carlo algorithms to compute the mutual 2 2 -SRE, overcoming limitations of previous approaches based on local update. We also give improved statevector simulation methods for Bell sampling and SREs with O(8^{N/2}) O ( 8 N / 2 ) time and O(2^N) O ( 2 N ) memory, which we demonstrate for 24 24 qubits. Our work uncovers improved approaches to study the complexity of quantum many-body systems.
Nonstabilizerness, also known as magic, plays a central role in universal quantum computation. Hypergraph states are nonstabilizer generalizations of graph states and constitute a key class of quantum states in various areas of quantum physics, such as the demonstration of quantum advantage, measurement-based quantum computation, and the study of topological phases. In this work, we investigate nonstabilizerness of 3-uniform hypergraph states, which are solely generated by controlled-controlled-Z gates, in terms of the stabilizer Rényi entropy (SRE). We find that the SRE of 3-uniform hypergraph states can be expressed using the matrix rank, which reduces computational cost from O(23N)\mathcal{O}(2^{3N})O(23N) to O(N32N)\mathcal{O}(N^3 2^{N})O(N32N) for NNN-qubit states. Based on this result, we exactly evaluate SREs of one-dimensional hypergraph states. We also present numerical results of SREs of several large-scale 3-uniform hypergraph states. Our results would contribute to an understanding of the role of nonstabilizerness in a wide range of physical settings where hypergraph states are employed.
The advent of quantum technologies brought forward much attention to the theoretical characterization of the computational resources they provide. A method to quantify quantum resources is to use a class of functions called magic monotones and stabilizer entropies, which are, however, notoriously hard and impractical to evaluate for large system sizes. In recent studies, a fundamental connection between information scrambling, the magic monotone mana and 2-Renyi stabilizer entropy was established. This connection simplified magic monotone calculation, but this class of methods still suffers from exponential scaling with respect to the number of qubits. In this work, we establish a way to sample an out-of-time-order correlator that approximates magic monotones and 2-Renyi stabilizer entropy. We numerically show the relation of these sampled correlators to different non-stabilizerness measures for both qubit and qutrit systems and provide an analytical relation to 2-Renyi stabilizer entropy. Furthermore, we put forward and simulate a protocol to measure the monotonic behaviour of magic for the time evolution of local Hamiltonians.
Grover's algorithm is a textbook example of quantum advantage, providing a quadratic query speedup over classical methods for unstructured search. In this Letter, we characterize the non-stabilizerness, or magic, developed throughout Grover's protocol, quantifying quantum complexity with respect to the efficiently simulable stabilizer states. First, we compute the compilation-independent magic at the end of each Grover iteration, deriving an analytic prediction for the stabilizer Rényi entropy and proving that it remains intensive as the system size grows. We then investigate the magic overhead due to decomposing the circuit into elementary gates. When the solution to the search problem is known, we show that an efficient decomposition exists that keeps magic bounded despite using an extensive number of Toffoli gates. In contrast, agnostic implementations are expected to generate volume-law non-stabilizerness, as we confirm for the 3-SAT problem, which rules out efficient simulation by stabilizer-based methods in practically relevant cases. Our findings clarify the growth of magic in Grover's algorithm and the role of solution-awareness in its circuit compilation.