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 that 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 nonstabilizer ness. Counterintuitively, 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.