= Solution
Let $w$ be the number of ones. The displayed output state assigns the outcome $(0,0)$ probability
$$
\boxed{\Pr(0,0)=\frac{(N-2w)^2}{N^2}.}
$$
For 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, \b[$(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 $\widehat x_i-\widehat x_j\ne0$, 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>.
Back to article page
