Computing quantum magic of state vectors

This paper introduces efficient, numerically exact algorithms based on the fast Hadamard transform to compute stabilizer Rényi entropy and mana for quantum states, offering an exponential improvement in computational complexity over naive methods and providing a high-performance, open-source Julia package (HadaMAG) to enable large-scale studies of quantum magic.

The Gist

Imagine you have a massive, complex machine made of tiny switches (quantum bits, or "qubits"). Some of these machines are very simple and predictable; you can describe them easily with a standard instruction manual. In the quantum world, we call these "boring" states Stabilizer States. They are like a well-oiled clockwork mechanism.

But then, you have other quantum states that are wild, chaotic, and incredibly complex. These are the "magic" states. They are the ones that give quantum computers their superpowers, allowing them to solve problems that would take classical supercomputers millions of years.

The problem? Measuring exactly how much "magic" a state has is incredibly difficult. It's like trying to count every single grain of sand on a beach to see how much of it is gold. The more sand (qubits) you have, the harder it gets. In fact, for a beach with just 20 grains, the math becomes so huge that even the world's fastest supercomputers would take years to finish the count.

The Problem: The "Sand Counting" Nightmare

The authors of this paper, Piotr Sierant and his team, tackled this counting problem. They wanted to measure two specific things:

1. SRE (Stabilizer Rényi Entropy): A measure of "magic" for standard qubits (like the ones in most quantum computers today).
2. Mana: A similar measure for "qutrits" (a slightly more complex type of quantum bit, like a three-sided coin instead of a two-sided one).

The old way of doing this was like trying to count every single grain of sand by picking them up one by one. If you added just a few more grains, the time it took to count them would explode exponentially. It was a dead end for large systems.

The Solution: The "Magic Flashlight" (Fast Hadamard Transform)

The team discovered a clever shortcut. Instead of counting every grain individually, they invented a "Magic Flashlight" (mathematically known as the Fast Hadamard Transform).

Imagine you have a dark room filled with millions of switches.

• The Old Way: You walk up to every single switch, flip it, check the light, write it down, and move to the next. This takes forever.
• The New Way: You turn on a special flashlight that illuminates the entire room at once, but in a very specific pattern. This pattern instantly tells you the average brightness of the whole room without you ever having to visit a single switch individually.

By using this "flashlight," the team's new algorithms can calculate the amount of "magic" in a quantum state exponentially faster.

• Old Speed: If you double the number of qubits, the time needed goes up by a factor of 8 (or more).
• New Speed: If you double the number of qubits, the time only goes up by a factor of 2 (roughly).

This means they can now analyze systems with 25 qubits (which is huge for this type of math) in a few hours, whereas the old methods would have taken longer than the age of the universe.

The Toolkit: HadaMAG.jl

The researchers didn't just write the math; they built a software toolbox called HadaMAG.jl. Think of this as a high-performance calculator app that anyone can use.

• It's open-source, meaning anyone can download it for free.
• It's supercharged, designed to run on massive supercomputers with thousands of processors and even specialized graphics cards (GPUs) to do the math in parallel.
• It handles both the "exact" counting (for smaller systems) and a "smart sampling" method (for larger systems).

The "Smart Sampling" Analogy:
Sometimes, even the flashlight is too slow for a beach the size of the Sahara. In those cases, the software uses a "Smart Sampling" technique. Instead of counting every grain, it takes a few representative handfuls of sand, analyzes them, and uses a statistical trick (thermodynamic integration) to guess the total gold content with high accuracy. This allows them to study even larger systems that were previously impossible to touch.

Why Does This Matter?

This isn't just about doing math faster. It's about understanding the "fuel" of the quantum revolution.

• Quantum Advantage: We need to know when a quantum computer is actually doing something a classical computer can't. This "magic" measure tells us exactly that.
• New Physics: It helps scientists study how quantum systems behave when they are chaotic, like in black holes or during the early moments of the universe.
• Future Tech: As we build bigger quantum computers, we need tools to check if they are working correctly. This paper provides the ruler to measure that complexity.

In a Nutshell

The authors took a problem that was mathematically "impossible" for large systems and solved it by finding a mathematical shortcut (the Fast Hadamard Transform). They turned a task that required counting every single grain of sand into a task that could be done by shining a special light. They packaged this into a free, powerful software tool, allowing scientists to finally measure the "magic" in large, complex quantum systems and understand the true potential of quantum computing.

Technical Summary

1. Problem Statement

Quantum "magic" (or non-stabilizerness) is a crucial resource for quantum advantage, quantifying how far a quantum state deviates from the set of stabilizer states (which can be efficiently simulated classically). Two primary measures of magic are:

• Stabilizer Rényi Entropy (SRE): For qubits ($d=2$).
• Mana: For qutrits ($d=3$) and generally odd prime dimensions.

The Challenge:
Calculating these measures for pure states represented as state vectors requires evaluating $d^{2N}$ expectation values of non-local operators (Pauli strings for SRE, phase-space point operators for Mana).

• Naive Approach: Direct evaluation scales as $O(d^{3N})$ in time complexity.
• Limitation: This exponential scaling restricts exact calculations to very small systems ($N \approx 15$ qubits/qutrits), far below the capabilities of modern state-vector simulators which can handle $N > 30$.
• Gap: While tensor-network methods exist for weakly entangled states, they fail for highly entangled states (e.g., in non-equilibrium dynamics or highly excited eigenstates) where state-vector representations are the only viable option.

2. Methodology

The authors introduce a suite of algorithms that leverage the Fast Hadamard Transform (FHT) and its generalizations to achieve exponential speedups.

A. Exact Algorithms for Pure States

The core insight is that the inner sums over "Z-type" operators (or phase-space indices) can be computed simultaneously using fast transforms rather than iteratively.

1. SRE for Qubits (Algorithm 2):

   • Concept: The SRE involves summing overlaps $\langle \psi | X_a Z_b | \psi \rangle^{2q}$. For a fixed $X_a$, the sum over all $Z_b$ corresponds to a Walsh–Hadamard Transform (Fourier transform over $\mathbb{Z}_2^N$) of the vector $v_x = \beta^*_x \alpha_x$ (where $\alpha, \beta$ are amplitudes of $|\psi\rangle$ and $X_a|\psi\rangle$).
   • Complexity: Reduces time from $O(8^N)$ to $O(N 4^N)$. Memory remains $O(2^N)$.
   • Parallelism: The outer loop over $X_a$ is trivially parallelizable.

2. Mana for Qutrits (Algorithm 5):

   • Concept: Analogous to the qubit case, but for $d=3$. The inner sum over phase-space indices is computed via a Fast Fourier Transform (FFT) over the additive group $\mathbb{Z}_3^N$ using a specific $3 \times 3$ "Hadamard" matrix $F_3$.
   • Complexity: Reduces time from $O(27^N)$ to $O(N 9^N)$. Memory remains $O(3^N)$.

B. Sampling Algorithm for SRE (Algorithm 3)

For systems where $N$ is too large even for the exact $O(N 4^N)$ scaling (e.g., $N > 25$), the authors propose a Monte Carlo estimator.

• Thermodynamic Integration: Instead of sampling Pauli strings directly (which suffers from exponential variance growth), they define a "regularized energy" $f_\epsilon(X_a)$ and integrate over an inverse temperature $\beta \in [0, 1]$.
• Hybrid Approach: The algorithm samples only the $X_a$ patterns using Metropolis-Hastings. For each sampled $X_a$, the full sum over $Z_b$ is computed exactly using the Fast Hadamard Transform.
• Benefit: This avoids the exponential variance growth of naive sampling. The statistical error scales polynomially with $N$ for generic states, requiring only a polynomial increase in samples to maintain precision.

C. Exact Algorithm for Mixed States (Algorithm 6)

• Context: Mana is a valid monotone for mixed states, but standard state-vector methods do not apply.
• Method: The authors construct a linear map $M$ (a $9 \times 9$ matrix for a single qutrit) such that the vector of all phase-space expectation values is $w = M^{\otimes N} \text{vec}(\rho)$.
• Implementation: They apply the tensor power $M^{\otimes N}$ in-place by sweeping over tensor indices (legs), avoiding the construction of the massive $9^N \times 9^N$ matrix.
• Complexity: Time $O(N 9^N)$, Memory $O(9^N)$ (dominated by the density matrix storage).

3. Key Contributions

1. Exponential Speedup: Developed algorithms that reduce the computational complexity of computing SRE and Mana from $O(d^{3N})$ to $O(N d^{2N})$. This is an exponential improvement in system size $N$.
2. State-Vector Optimization: Unlike previous methods requiring density matrices or Pauli vectors (which consume $O(d^{2N})$ memory), these algorithms operate directly on state vectors with memory overhead $O(d^N)$.
3. Hybrid Sampling: Introduced a sampling scheme for SRE that combines Monte Carlo sampling with exact fast transforms, enabling the estimation of magic for larger systems ($N \approx 30$) with controlled statistical error.
4. Mixed-State Extension: Provided the first efficient exact algorithm for computing Mana for mixed states of qutrits.
5. Open-Source Software (HadaMAG.jl): Implemented all algorithms in a high-performance Julia package supporting:
   • Multi-threading.
   • MPI-based distributed parallelism.
   • GPU acceleration (CUDA).

4. Results and Benchmarks

The authors benchmarked their methods on random quantum circuits (Haar-random brick-wall circuits) using the HadaMAG.jl package.

• Exact SRE (Qubits):
  • Achieved exact computation for $N=25$ qubits in ~2 hours using 8 nodes with 4 GPUs each.
  • Comparison: A naive implementation is limited to $N=16$ within the same wall-clock time.
  • Scaling: The exact algorithm allows calculations up to $N=22$ on a single high-core node (112 cores) in under an hour.
• Exact Mana (Qutrits):
  • Computed exact Mana for $N=15$ qutrits in ~11 hours using 8 nodes.
  • Mixed-state Mana: Computed for subsystems up to $N_A=10$ qutrits in minutes (limited by memory for the density matrix, not the algorithm speed).
• Sampling Accuracy:
  • For $N=16$, the sampling algorithm (with 1000 samples) reproduced the exact SRE with an error of $\sim 5.5 \times 10^{-5}$.
  • Variance analysis showed that the number of samples required to maintain fixed precision grows only polynomially with $N$, unlike the exponential growth in naive sampling.

5. Significance

• Bridging the Gap: These methods enable the study of "magic" in regimes previously inaccessible: highly entangled, non-equilibrium states in systems with $N > 25$ qubits/qutrits.
• Resource Theory: Provides a practical tool for quantifying the quantum resources necessary for computational advantage in many-body systems.
• Applications: The tools are immediately applicable to:
  • Non-equilibrium dynamics of quantum circuits.
  • Eigenstate properties of ergodic and many-body localized (MBL) systems.
  • Quantum chaos and thermalization.
  • Lattice gauge theories and constrained dynamics.
• Scalability: By combining exact fast transforms with efficient sampling and GPU acceleration, the work sets a new standard for numerical investigations of non-stabilizerness, moving beyond the limitations of tensor networks for highly entangled states.

In summary, this work transforms the computation of quantum magic from a bottleneck limited to small systems into a scalable, high-performance procedure capable of handling large-scale quantum many-body problems.