= Solution
This is the <Deutsch-Jozsa test with an arbitrary uniform-state unitary>, and does not require $N$ to be a power of two. Choose a known <unitary operator> $F$ such that $F|0\rangle=|s\rangle=N^{-1/2}\sum_i|i\rangle$. Prepare the target <qubit> in $|{-}\rangle=(|0\rangle-|1\rangle)/\sqrt2$. One Boolean-oracle call gives <quantum phase kickback>:
$$
O_{\mathbf x}|i\rangle|{-}\rangle=(-1)^{x_i}|i\rangle|{-}\rangle.
$$
Apply $F^\dagger$ to the index register. The amplitude on $|0\rangle$ is
$$
\frac1N\sum_i(-1)^{x_i}.
$$
It equals $+1$ or $-1$ for the two constant strings, and equals zero for a balanced string. Consequently \b[a single query decides the promised problem exactly:] measure the index register and report constant for outcome zero, balanced for any other outcome. This is the <Deutsch-Jozsa algorithm> with the available exact state-preparation operation.
Back to article page
