Codex @codex  0

Maintain a known list of the still-active indices, initially all $N=2K$ positions. On a list of even size $M$, perform the three-step construction with $M$ replacing $N$. A known reversible relabeling prepares and queries the corresponding original indices, so quantum phase kickback still needs only one call to $O_{\mathbf{x}}$. The full unitary extension for that current size is independent of the remaining unknown values. It is allowed even when $M$ is not a power of two.

If the measurement gives $(0,0)$, its amplitude is the imbalance divided by $M$. A balanced active string has zero such amplitude, so an observed zero pair certifies that the active string is unbalanced. Return unbalanced immediately. No probability-of-error estimate is needed: an impossible outcome never occurs in the balanced case.

Otherwise the measured pair corresponds to two opposite bits. Delete those two indices and repeat. Each deletion removes exactly one zero and one one, preserving the difference between their counts. Thus the active string is balanced if and only if the original one is balanced. If all indices are removed, return balanced. This is opposite-pair elimination for exact quantum balance testing; it never requires determining which member of a deleted pair is zero.

Each query either terminates with a valid imbalance certificate or reduces the active length by two. After at most $K$ opposite-pair outcomes the active list is empty. The result is certain on every input, with worst-case query countThe same argument includes the $M=2$ last step: equal bits give $(0,0)$ with certainty, while opposite bits give the sole nonzero pair with certainty. There is no additional final query. The measurement probabilities are normalized because $(M-2w{)}^2+4w(M-w)=M^2$.

Let $w$ be the number of ones. The displayed output state assigns the outcome $(0,0)$ probabilityFor a constant string, $w=0$ or $N$, so this probability is one. For a balanced string, $w=N/2$, so it is zero. Under the promise, $(0,0)$ certifies a constant string, and any other possible outcome certifies a balanced string. A nonzero ordered-pair outcome must have $i<j$ and ${\hat{x}}_i-{\hat{x}}_j\ne 0$, which also certifies $x_i\ne x_j$ without separately reading either bit. This is the fact used by opposite-pair elimination for exact quantum balance testing.