Classical Feedback Closed a Quadratic Gap in Stabilizer Learning

A classical feedback loop can remove a seemingly expensive quantum-measurement requirement from one important learning task. Researchers proved that an unknown pure stabilizer state on n qubits can be identified with a number of sequential single-copy measurements that grows only linearly with n, without ever holding two copies coherently for a joint measurement.^[1][2]

The result closes a sharp complexity gap. Bell sampling was already known to learn a stabilizer state from Theta(n) copies, but it jointly measures corresponding qubits from two copies. Non-adaptive single-copy strategies, whose measurement choices ignore earlier outcomes, require Omega(n squared) copies on a subclass. The new adaptive protocol recovers the linear scaling.^[1][2]

The key step uses two fresh copies in a round but measures them separately in the computational basis. The protocol takes the bitwise difference between the two classical outcomes and uses that information to choose the next Clifford operation. No Bell measurement or coherent quantum memory between the copies is required; the advantage comes from changing later measurements in response to earlier data.^[2]

Each successful update converts another stabilizer into a diagonal, Z-type stabilizer while preserving those already found. Once all n independent stabilizers have been brought into that form, the transformed state is a computational-basis state that can be read directly. Tracking the accumulated Clifford operations then reconstructs the original stabilizer state.^[2]

The paper also gives a single-copy stabilizer tester with Theta(n plus 1 over epsilon) copy complexity, matching the lower bound for distinguishing stabilizer states from states at least epsilon away. A separate memory tradeoff says that storing k coherent qubits changes the optimal testing cost to Theta(n minus k plus 1 over epsilon).^[1][2]

That tradeoff places a useful boundary around small quantum memories. For constant accuracy, the authors find that testing remains linear in n until the protocol can preserve nearly the entire n-qubit state. A modest memory does not by itself unlock the constant-copy behavior available when a full copy can be kept for a collective measurement.^[2]

The adaptive mechanism extends beyond exact stabilizer states, but the price becomes explicit. For pure states with stabilizer nullity r, including states made by Clifford circuits with a bounded number of non-Clifford T gates, the paper gives an O(n times 2 to the r) learning cost at constant accuracy and confidence. That exponential dependence limits the extension as non-stabilizer structure grows.^[1][2]

This is a theory preprint, not a hardware demonstration. The cleanest learning theorem assumes an exact pure stabilizer state, ideal Clifford operations and fresh preparations; tolerant learning needs a sufficiently large stabilizer fidelity. The practical next step is to test whether measurement noise, imperfect feedback and state-preparation drift preserve the predicted copy savings on experimental systems.^[1][2]