  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.
