Phase transition in stabilizer entropy and efficient purity estimation

Stabilizer entropy (SE) quantifies the spread of a state in the basis of Pauli operators. It is a computationally tractable measure of nonstabilizerness and thus a useful resource for quantum computation. SE can be moved around a quantum system, effectively purifying a subsystem from its complex features. We show that there is a phase transition in the residual subsystem SE as a function of the density of non-Clifford resources. This phase transition has important operational consequences: it marks the onset of a subsystem purity estimation protocol that requires poly(n)exp(t) many queries to a circuit containing t non-Clifford gates that prepares the state from a stabilizer state. Then, for t=O(log2n), it estimates the purity with polynomial resources, and, for highly entangled states, attains an exponential speed-up over the known state-of-the-art algorithms.