A fast and exact approach for stabilizer Rényi entropy via the XOR-FWHT algorithm
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
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, 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.