G. Passarelli, R. Fazio, P. Lucignano (Feb 14 2024).
Abstract: Typical measures of nonstabilizerness of a system of $N$ qubits require computing $4^N$ expectation values, one for each Pauli string in the Pauli group, over a state of dimension $2^N$. In this Letter, we show that, if the system is invariant under permutations, this resource overhead can be exponentially decreased to $O(N^3)$ expectation values on a state with a dimension $O(N)$, allowing for a polynomial-time evaluation of the nonstabilizerness up to hundreds of qubits.