Nonstabilizerness via Perfect Pauli Sampling of Matrix Product States

We introduce a novel approach to evaluate the nonstabilizerness of an N-qubits matrix product state (MPS) with bond dimension χ. In particular, we consider the recently introduced stabilizer Rényi entropies (SREs). We show that the exponentially hard evaluation of the SREs can be achieved by means of a simple perfect sampling of the many-body wave function over the Pauli string configurations. The sampling is achieved with a novel MPS technique, which enables us to compute each sample in an efficient way with a computational cost O (Nχ^3). We benchmark our method over randomly generated magic states, as well as in the ground-state of the quantum Ising chain. Exploiting the extremely favorable scaling, we easily have access to the nonequilibrium dynamics of the SREs after a quantum quench.