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.
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.
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 O(2N) 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 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(Nd2N), providing an exponential improvement over the naive 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 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 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.
We study the emergence of complexity in deep random N -qubit T -gate-doped Clifford circuits, as reflected in their spectral properties and in magic generation, characterized by the stabilizer Rényi entropy distribution and the nonstabilizing power of the circuit. For pure (undoped) Clifford circuits, a unique periodic orbit structure in the space of Pauli strings implies peculiar spectral correlations and level statistics with large degeneracies. T -gate doping induces an exponentially fast transition to chaotic behavior, described by random matrix theory. We compare these complexity indicators with magic generation properties of the Clifford + T ensemble, and determine the distribution of magic, as well as the average nonstabilizing power of the quantum circuit ensemble. In the dilute limit, N T ≪ N , magic generation is governed by single-qubit behavior. Magic is generated in approximate quanta, increases approximately linearly with the number of T gates, N T , and displays a discrete distribution for small N T . At N T ≈ N , the distribution becomes quasicontinuous, and for N T ≫ N , it converges to that of Haar-random unitaries, and averages to a finite magic density, m 2 , lim N → ∞ 〈 m 2 〉 Haar = 1 . This is in contrast to the spectral transition, where O ( 1 ) T gates suffice to remove spectral degeneracies and to induce a transition to chaotic behavior in the thermodynamic limit. Magic is therefore a more sensitive indicator of complexity.