{"id":"arxiv/2601.00761","url":"https://arxiv.org/abs/2601.00761","tags":["quant-ph","cond-mat.mes-hall","cond-mat.stat-mech"],"score":0,"title":"Exponentially Accelerated Sampling of Pauli Strings for Nonstabilizerness","domain":"quant-ph","source":"arxiv","authors":["Zhenyu Xiao","Shinsei Ryu"],"reviews":0,"subject":"quant-ph","summary":"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 $\\mathcal{O}(2^N)$ to $\\mathcal{O}(N)$. We further develop a Monte Carlo estimator with Clifford preconditioning and find that the required number of samples…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-01-02","reactions":{}}