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:2512.24685 · Physical Review Research

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

Xuyang Huang, Han-Ze Li, Jian-Xin Zhong

quant-phSubmitted Dec 31, 2025• Announced Jan 1, 2026• 0 citations
v1 · Dec 31, 2025v2 · Jan 5, 2026v3 · Mar 25, 2026
arXivHTMLPDF

Abstract

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, a direct brute-force enumeration of all Pauli strings and the corresponding expectation values from a length-$2^N$ state vector, where $N$ is the system size, yields an overall computational cost scaling as $O(8^N)$, which quickly becomes infeasible as the system size grows. Here we reformulate the second-order stabilizer Rényi entropy in a bitstring language, expose an underlying XOR-convolution structure on $\mathbb Z_2^N$, and reduce the computation to $2^N$ fast Walsh-Hadamard transforms of length, together with pointwise operations, yielding a deterministic and exact XOR fast Walsh-Hadamard transforms algorithm with runtime scaling $O(N4^N)$ and natural parallelism. This algorithm enables high-precision, medium-scale exact calculations for generic state vectors. It provides a practical tool for probing the scaling, phase diagnostics, and dynamical fine structure of quantum magic in many-body systems.

Related papers

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

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

Amortized Stabilizer Rényi Entropy of Quantum Dynamics

Chengkai Zhu, Yu-Ao Chen, Zanqiu Shen +3 more

Unraveling the secrets of how much nonstabilizerness a quantum dynamic can generate is crucial for harnessing the power of magic states, the essential resources for achieving quantum advantage and realizing fault-tolerant quantum computation. In this work, we introduce the amortized $α$-stabilizer Rényi entropy, a magic monotone for unitary operations that quantifies the nonstabilizerness generation capability of quantum dynamics. Amortization is key in quantifying the magic of quantum dynamics, as we reveal that nonstabilizerness generation can be enhanced by prior nonstabilizerness in input states when considering the $α$-stabilizer Rényi entropy, while this is not the case for robustness of magic or stabilizer extent. We demonstrate the versatility of the amortized $α$-stabilizer Rényi entropy in investigating the nonstabilizerness resources of quantum dynamics of computational and fundamental interest. In particular, we establish improved lower bounds on the $T$-count of quantum Fourier transforms and the quantum evolutions of one-dimensional Heisenberg Hamiltonians, showcasing the power of this tool in studying quantum advantages and the corresponding cost in fault-tolerant quantum computation.

arXiv:2409.06659•Sep 10, 2024•0 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•Jan 5, 2026•0 citations

Nonequilibrium quantum Monte Carlo algorithm for stabilizer Rényi entropy in spin systems

Zejun Liu, Bryan K. Clark

Quantum magic, or nonstabilizerness, provides a crucial characterization of quantum systems, regarding the classical simulability with stabilizer states. In this work, we propose an alternative and efficient algorithm for computing stabilizer R\'enyi entropy, one of the measures for quantum magic, in spin systems with sign-problem free Hamiltonians. This algorithm is based on the quantum Monte Carlo simulation of the path integral of the work between two partition function ensembles and it applies to all spatial dimensions and temperatures. We demonstrate this algorithm on the one- and two-dimensional transverse field Ising model at both finite and zero temperatures and show the quantitative agreements with tensor-network based algorithms. We analyze the computational cost and provide analytical and numerical evidences for it to be polynomial in system size. This work also suggests a unifying framework for calculating various types of entropy quantities including entanglement R\'enyi entropy and entanglement R\'enyi negativity.

arXiv:2405.19577•Physical review. B./Physical review. B•Feb 20, 2025•17 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
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, a direct brute-force enumeration of all Pauli strings and the corresponding expectation values from a length-2N2^N2N state vector, where NNN is the system size, yields an overall computational cost scaling as O(8N)O(8^N)O(8N), which quickly becomes infeasible as the system size grows. Here we reformulate the second-order stabilizer Rényi entropy in a bitstring language, expose an underlying XOR-convolution structure on Z2N\mathbb Z_2^NZ2N​, and reduce the computation to 2N2^N2N fast Walsh-Hadamard transforms of length, together with pointwise operations, yielding a deterministic and exact XOR fast Walsh-Hadamard transforms algorithm with runtime scaling O(N4N)O(N4^N)O(N4N) and natural parallelism. This algorithm enables high-precision, medium-scale exact calculations for generic state vectors. It provides a practical tool for probing the scaling, phase diagnostics, and dynamical fine structure of quantum magic in many-body systems.
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.
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.
Unraveling the secrets of how much nonstabilizerness a quantum dynamic can generate is crucial for harnessing the power of magic states, the essential resources for achieving quantum advantage and realizing fault-tolerant quantum computation. In this work, we introduce the amortized ααα-stabilizer Rényi entropy, a magic monotone for unitary operations that quantifies the nonstabilizerness generation capability of quantum dynamics. Amortization is key in quantifying the magic of quantum dynamics, as we reveal that nonstabilizerness generation can be enhanced by prior nonstabilizerness in input states when considering the ααα-stabilizer Rényi entropy, while this is not the case for robustness of magic or stabilizer extent. We demonstrate the versatility of the amortized ααα-stabilizer Rényi entropy in investigating the nonstabilizerness resources of quantum dynamics of computational and fundamental interest. In particular, we establish improved lower bounds on the TTT-count of quantum Fourier transforms and the quantum evolutions of one-dimensional Heisenberg Hamiltonians, showcasing the power of this tool in studying quantum advantages and the corresponding cost in fault-tolerant quantum computation.
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.
Quantum magic, or nonstabilizerness, provides a crucial characterization of quantum systems, regarding the classical simulability with stabilizer states. In this work, we propose an alternative and efficient algorithm for computing stabilizer R\'enyi entropy, one of the measures for quantum magic, in spin systems with sign-problem free Hamiltonians. This algorithm is based on the quantum Monte Carlo simulation of the path integral of the work between two partition function ensembles and it applies to all spatial dimensions and temperatures. We demonstrate this algorithm on the one- and two-dimensional transverse field Ising model at both finite and zero temperatures and show the quantitative agreements with tensor-network based algorithms. We analyze the computational cost and provide analytical and numerical evidences for it to be polynomial in system size. This work also suggests a unifying framework for calculating various types of entropy quantities including entanglement R\'enyi entropy and entanglement R\'enyi negativity.
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.