Learning the stabilizer group of a Matrix Product State

We present a novel classical algorithm designed to learn the stabilizer group – namely the group of Pauli strings for which a state is a $\pm 1$ eigenvector – of a given Matrix Product State (MPS). The algorithm is based on a clever and theoretically grounded biased sampling in the Pauli (or Bell) basis. Its output is a set of independent stabilizer generators whose total number is directly associated with the stabilizer nullity, notably a well-established nonstabilizer monotone. We benchmark our method on $T$-doped states randomly scrambled via Clifford unitary dynamics, demonstrating very accurate estimates up to highly-entangled MPS with bond dimension $\chi \sim {10}^3$. Our method, thanks to a very favourable scaling $\mathcal{O}({\chi }^3)$, represents the first effective approach to obtain a genuine magic monotone for MPS, enabling systematic investigations of quantum many-body physics out-of-equilibrium.