= Solution
With the restricted operations, begin in $|0\rangle|0\rangle$ and apply $F$ to the first register:
$$
\frac1{\sqrt N}\sum_i|i\rangle|0\rangle.
$$
Now apply
$$
O_x,\qquad Z,\qquad O_x.
$$
For every basis state this <compute-phase-uncompute construction> acts as
$$
|i\rangle|0\rangle
\mapsto |i\rangle|x_i\rangle
\mapsto(-1)^{x_i}|i\rangle|x_i\rangle
\mapsto(-1)^{x_i}|i\rangle|0\rangle.
$$
The first register is therefore the same phase state used in part (a). Apply $F^{-1}$ and measure. Again, outcome $0$ occurs with probability one for a constant string and probability zero for a balanced string. The construction uses exactly two queries to $O_x$ and only the permitted operations.
Back to article page
