Exponentially Accelerated Sampling of Pauli Strings for Nonstabilizerness

Quantum magic, quantified by nonstabilizerness, measures departures from stabilizer structure and underlies potential quantum speedups. We introduce an efficient classical algorithm that exactly computes stabilizer Rényi entropies and stabilizer nullity for generic many-body wavefunctions of N qubits. The method combines the fast Walsh-Hadamard transform with an exact partition of Pauli operators. It achieves an exponential speedup over direct approaches, reducing the average cost per sampled Pauli string from O\(2^N\) to O(N). Building on this framework, we further develop a Monte-Carlo estimator for stabilizer Rényi entropies together with a Clifford-based variance-reduction scheme that suppresses sampling fluctuations. We benchmark the accuracy and efficiency on ensembles of random magic states, and apply the method to random Clifford circuits with doped T gates, comparing different doping architectures. Our approach applies to arbitrary quantum states and provides quantitative access to magic resources both encoded in highly entangled states and generated by long-time nonequilibrium dynamics.