PaperlayerView exact revision on arXiv

Source-linked AI summary

Computing quantum magic of state vectors

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

arXiv:2601.07824v3quant-phcond-mat.dis-nncond-mat.stat-mech

TL;DR

Existing SRE and mana calculations remain expensive for large or highly entangled state vectors. The paper uses fast Hadamard-transform methods to compute these measures efficiently, achieving O(Nd2N) cost instead of O(d3N), while also extending the approach to sampling-based SRE and mixed-state mana.

  • Problem

    Direct SRE and mana evaluation requires d2N expectation values, limiting calculations for large or highly entangled state vectors beyond tensor-network regimes.

  • Method

    The paper develops fast-transform algorithms for exact pure-state SRE and mana, a sampling estimator for SRE, and a mixed-state mana method.

  • Results

    O(Nd2N) cost replaces naive O(d3N) scaling for the main algorithms, with exact computations demonstrated up to N = 25 qubits and N = 15 qutrits.

  • Takeaways & Limitations

    The state-vector algorithms complement tensor-network methods by requiring no low-entanglement assumption and provide tools for large-scale studies of magic dynamics.

  • Takeaways & Limitations

    The sampling estimator can suffer amplified uncertainty when ε is finite and relevant SRE contributions vanish, potentially causing exponential growth in estimation error.

Abstract

from arXiv · show

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.

1 Introduction

Non-stabilizerness measures quantify a quantum state's departure from stabilizer states, but their evaluation becomes difficult for large or highly entangled systems. This work develops fast state-vector algorithms for SRE and mana, extending exact and sampling-based calculations to larger systems.

  • Non-stabilizerness measures quantify resources associated with departures from the stabilizer set and are relevant to quantum advantage and many-body-state complexity.
  • Many established non-stabilizerness measures require costly optimization procedures that become prohibitive for systems with fewer than N = 10 qubits.
  • The SRE for qubits and mana for qutrits avoid explicit minimization, enabling studies across quantum phases, dynamics, and other many-body settings.
  • Direct evaluation of SRE and mana requires d2N expectation values and is feasible for state vectors only up to N ≈15 qubits, while tensor-network methods target weakly entangled states.
  • Highly entangled states can have state-vector representations beyond N = 30 qubits, exceeding the practical range of direct SRE evaluation and tensor-network methods.
  • Fast-Hadamard-transform algorithms compute SRE and mana exactly at improved cost, support sampling-based SRE estimation and mixed-state mana, and enable up to N = 25 qubits and N = 15 qutrits.

2 Non-stabilizerness measures

The section defines qubit SRE and qutrit mana as non-stabilizerness measures built from generalized Pauli structures. It states their key resource-theoretic properties and the computational role of their expectation-value representations.

  • Qubit Pauli strings are tensor products of I, X, Y, and Z operators, and stabilizer states arise from Clifford operations on |0⟩⊗N.
  • The SRE is defined for pure N-qubit states through a Rényi-indexed sum over all 4N Pauli-string expectation values.
  • The SRE is faithful and Clifford invariant, and alternative measures such as robustness of magic and stabilizer extent require minimization procedures.
  • For integer q ≥2, the SRE is a pure-state stabilizer monotone, while for 0 < q < 2 it may increase under stabilizer protocols.
  • For qutrits, generalized Pauli operators define phase-space point operators and a discrete Wigner function whose negativity yields mana.
  • Mana is faithful for qutrit systems and satisfies Clifford invariance, additivity, and monotonicity for pure and mixed states.

3 Algorithms for computation of SRE and mana

Evaluating SRE and mana requires exponentially many Pauli-string or phase-space expectation values. The algorithms in this section target efficient computation of these quantities for state-vector representations.

  • SRE and mana require computing d2N expectation values of Pauli strings and phase-space point operators, respectively.
  • Because the number of required expectation values grows rapidly with N, direct evaluation becomes computationally prohibitive for larger systems.
  • The section introduces efficient evaluation algorithms for SRE and mana when quantum states are represented as state vectors.

3.1 Calculation of SRE for qubits

The qubit SRE calculation is accelerated by replacing repeated Pauli-string updates with fast Hadamard transforms. This changes the exact algorithm's scaling from O(8N) to O(N4N) while retaining state-vector memory scaling.

  • Naive SRE calculation: The naive method enumerates Pauli strings in Gray-code order, updating the transformed state with one X or Z operator per step.
  • Naive SRE calculation: The naive algorithm evaluates 4N overlaps and updates at cost O(2N) each, giving overall time complexity O(8N) and memory footprint O(2N).
  • Efficient exact SRE: Each Pauli string can be decomposed as XaZb, separating the X-pattern from the Z-pattern in the SRE computation.
  • Efficient exact SRE: For fixed Xa, a single fast Hadamard transform replaces the inner sweep over all Z-strings and computes the corresponding overlaps together.
  • Efficient exact SRE: The fast Hadamard transform evaluates each fixed-X computation in O(N2N), yielding total cost O(N4N) instead of O(8N).
  • Efficient exact SRE: The exact algorithm uses O(2N) memory and its loop over X-patterns can be split into independently evaluated chunks for parallelism.

3.2 Monte Carlo sampling algorithm for SRE

The sampling scheme uses fast Hadamard transforms and thermodynamic integration to estimate SRE while reducing the sampling effort from exponential to polynomial growth for generic states. Regularization and symmetry handling determine stability and efficiency.

  • Comparison with direct sampling: Direct Pauli-string sampling can require exponentially many samples for fixed precision when SRE moments decay exponentially with N.The thermodynamic-integration approach is designed to avoid this worst-case behavior for generic states.
  • Fast-Hadamard-enhanced sampling: Fast Hadamard transforms obtain all Pauli-string expectation values for each fixed X-string, accelerating the sampling procedure.A single transform over Z-strings supplies the expectation values needed for each fixed X-string.
  • Thermodynamic integration: The estimator samples X-strings from a Boltzmann distribution and integrates expectation values over an auxiliary inverse temperature β.The energy is regularized when sector contributions vanish, and Metropolis–Hastings sampling estimates the integrand on a β grid.
  • Sampling error: For generic states with positive sector weights, the sampling effort required for fixed SRE precision grows polynomially with system size.Empirically, the variance scales at most as O(N^2), while the estimator uncertainty decreases as 1/√n_eff up to polynomial factors.
  • Limitations and symmetries: If S(a) vanishes, finite regularization can amplify uncertainty and may cause exponential error growth when ε must decrease with the vanishing sector weight.Known symmetries can restrict sampling to non-vanishing sectors; otherwise ε > 0 is a fallback with reduced sampling efficiency.
  • Computational cost: O(N2^N) operations per Monte Carlo update make the algorithm quasi-linear in the Hilbert-space dimension 2^N, rather than explicitly iterating over all 4^N Pauli strings.The dominant cost comes from EvalEnergy calls inside the Markov chains.

3.3 Calculation of mana for pure qutrit states

The pure-state mana algorithm replaces the costly sweep over all qutrit phase-space operators with a fast tensor-product Fourier transform. This reduces the runtime from O(27^N) to O(N9^N) while retaining O(3^N) memory.

  • Problem setup: Pure-state mana requires evaluating 9^N overlaps with phase-space point operators for an N-qutrit state.The operators are indexed by pairs of ternary strings and can be traversed with a ternary Gray code.
  • Naive calculation: The naive Gray-code sweep costs O(27^N) because each of the 9^N overlaps requires O(3^N) work.The memory cost is O(3^N), dominated by storing state vectors and work arrays.
  • Fast-transform method: For each fixed ternary X-index, the inner phase-space sweep is a tensor-product Fourier transform over Z_3^N.The transform is the qutrit analogue of the qubit Hadamard-transform relation.
  • Complexity: O(N9^N) runtime replaces the naive O(27^N) approach, while memory remains O(3^N).The fast transform reduces the inner-loop cost from O(9^N) to O(N3^N), with O(3^N) outer iterations.

3.4 Mana of mixed states via a fast tensor-product transform

For mixed qutrit states, mana is computed by transforming the vectorized density matrix with a tensor power of a fixed 9 × 9 matrix. The exact algorithm computes all phase-space expectation values in O(N9^N) time and O(9^N) memory.

  • Significance: Mana remains a faithful non-stabilizerness monotone for mixed qutrit states, making this exact mixed-state calculation particularly relevant.The paper presents the transform specifically to enable efficient evaluation in the mixed-state setting.
  • Mixed-state target: Mana for a mixed N-qutrit state is obtained by summing the absolute values of 9^N discrete-Wigner expectation values Tr(ρA_u).Unlike pure states, mixed states require traces rather than state-vector overlaps.
  • Tensor-product transform: The full collection of expectation values is a tensor-product linear map acting on the vectorized density matrix.The map factorizes as M^⊗N, where M is a fixed 9 × 9 single-qutrit matrix composed of Fourier blocks.
  • Implementation: The algorithm applies M^⊗N in place by sweeping over tensor legs and transforming fibers of nine entries.This avoids explicitly forming the 9^N × 9^N transform matrix.
  • Complexity: O(N9^N) operations and O(9^N) memory are sufficient for exact mixed-state mana computation.Each tensor leg costs O(9^N), and there are N legs; memory is dominated by the vectorized density matrix.

4 Examples and benchmarks

Benchmarks show that HadaMAG.jl computes exact SRE and mana for substantially larger qubit and qutrit systems by combining fast-transform algorithms with parallel and GPU backends. Its sampling estimator provides a practical alternative when exact SRE evaluation becomes too costly, while memory remains an important constraint for mixed-state mana.

  • Benchmark setup: Random brick-wall circuits provide highly entangled benchmark states for qubit and qutrit state-vector calculations.The circuits use Haar-random two-qudit gates arranged in a one-dimensional brick-wall architecture.
  • Exact SRE: 0, 5.519, and 13.985 are the reported SRE values for 16-qubit circuit depths 0, 1, and 16, respectively.The initial product state has zero SRE, while increasing circuit depth drives the SRE toward the Haar-random-state value.
  • Exact SRE: N = 22 qubits can be computed in under one hour, versus N = 16 for the naive implementation at the same wall time.The fast-Hadamard implementation parallelizes the Gray-code work and delivers nearly ideal speedup as core count increases.
  • Parallel and GPU execution: N = 25 qubits can be computed in roughly 2 hours using eight nodes with four GPUs per node.GPU offloading provides a substantial gain for system sizes N ≳ 18, while MPI and CUDA backends support distributed execution.
  • Sampling SRE: The sampling estimator requires a relatively mild quadratic increase in sample count with system size for random-circuit states.The variance grows linearly with N beyond a depth-dependent threshold, decreases with circuit depth, and the estimator error follows n_S^-1/2.
  • Mana calculation: N = 15 qutrits takes about 11 hours on eight nodes, while mixed-state mana reaches subsystems of N_A = 10 qutrits within a few minutes.Mixed-state mana currently has only a serial backend, and its larger-subsystem boundary is set mainly by storing the full density matrix.

5 Conclusion

The work develops fast-transform algorithms for exact and sampling-based evaluation of SRE and mana, extending them to pure and mixed states while retaining favorable complexity and memory scaling. Implemented in HadaMAG.jl, these methods target large-scale studies of non-stabilizerness, especially when state vectors are available for strongly entangled systems.

  • Algorithms and complexity: O(Nd2N) time and O(dN) memory characterize the exact SRE and mana algorithms, improving on naive O(d3N) schemes without extra memory overhead.The algorithms evaluate all d2N expectation values while retaining the state-vector-scale memory footprint.
  • Software and applications: HadaMAG.jl provides multithreading, MPI-based distributed parallelism, and CUDA GPU acceleration for the introduced routines.These implementations support numerically exact calculations beyond naive implementations.
  • Algorithms and complexity: Fast Walsh–Hadamard and ternary transforms unify the qubit SRE and qutrit mana calculations through Pauli-overlap and phase-space evaluations.The qubit case uses transforms on Z2^N, while the qutrit case uses fast Fourier transforms on Z3^N.
  • Sampling and mixed states: Thermodynamic integration combined with fast-Hadamard-based effective energies provides a sampling scheme for SRE that avoids exponential growth in required samples with system size.The scheme samples X-patterns and collapses the Z-pattern sum using a fast transform.
  • Sampling and mixed states: A structured, tensor-factorized linear map extends the fast-transform strategy to mana for mixed qutrit states.The map connects vectorized density matrices to phase-space expectation values and can be applied in place.
  • Complexity and outlook: The exact algorithms are close to computationally optimal because they access the full generalized Pauli spectrum at O(Nd2N) cost and linear-in-N cost per expectation value.The same near-optimal scaling applies to the sampling and mixed-state settings up to polynomial factors.
  • Complexity and outlook: State-vector methods complement tensor-network approaches by making no low-entanglement assumption and targeting explicitly available wave functions.This makes them suited to strongly entangled regimes where tensor-network-based calculations are less applicable.
  • Complexity and outlook: The exact and sampling tools establish a practical baseline for large-scale studies of magic dynamics and resource distribution across many-body platforms.The fast-transform perspective also motivates extensions to higher dimensions, other measures, and experimental post-processing.

A Relation to FWHT-based approaches in prior work

The paper distinguishes its state-vector algorithms from prior FWHT-based methods by avoiding full density matrices and Pauli vectors, while extending the approach from qubits to qutrits. This yields O(Nd2N) time and O(dN) memory for direct SRE and mana evaluation.

  • Prior approaches: Prior FWHT-based approaches target non-stabilizerness or Pauli decompositions using full density matrices or Pauli vectors as input.Their purposes include overlap evaluation, stabilizerness measures, and general operator decomposition.
  • Prior approaches: O(4N) memory is required by the density-matrix and full-Pauli-vector approaches, limiting their suitability for state-vector inputs at large N.Some prior routines also enumerate exponentially many stabilizer groups or require full operator matrices.
  • Present work: The present algorithms compute SRE and mana directly from dN-dimensional state vectors with O(Nd2N) time and O(dN) memory.They avoid constructing a density matrix or Pauli vector; the mixed-state mana algorithm instead applies its transform in place to a density matrix.
  • Present work: The mana algorithms extend the fast-transform strategy beyond prior qubit-only FWHT approaches to qutrits with d = 3.Algorithm 3 also maintains O(2N) memory while sampling over X-patterns and evaluating each Z-sum through one fast transform.
Loading 2601.07824v3…