Efficient quantum algorithms for stabilizer entropies

Stabilizer entropies (SEs) are measures of nonstabilizerness or `magic' that quantify the degree to which a state is described by stabilizers. SEs are especially interesting due to their connections to scrambling, localization and property testing. However, applications have been limited so far as previously known measurement protocols for SEs scale exponentially with the number of qubits. Here, we efficiently measure SEs for integer R\'enyi index $n>1$ via Bell measurements. The SE of $N$-qubit quantum states can be measured with $O(n)$ copies and $O(nN)$ classical computational time, where for even $n$ we additionally require the complex conjugate of the state. We provide efficient bounds of various nonstabilizerness monotones which are intractable to compute beyond a few qubits. Using the IonQ quantum computer, we measure SEs of random Clifford circuits doped with non-Clifford gates and give bounds for the stabilizer fidelity, stabilizer extent and robustness of magic. We provide efficient algorithms to measure Clifford-averaged $4n$-point out-of-time-order correlators and multifractal flatness. With these measures we study the scrambling time of doped Clifford circuits and random Hamiltonian evolution depending on nonstabilizerness. Counter-intuitively, random Hamiltonian evolution becomes less scrambled at long times which we reveal with the multifractal flatness. Our results open up the exploration of nonstabilizerness with quantum computers.