= Solution
Use the available unitaries to prepare
$$
|s\rangle=\frac1{\sqrt N}\sum_{i\in\mathbb Z_N}|i\rangle
$$
in the first register and
$$
|-\rangle=\frac{|0\rangle-|1\rangle}{\sqrt2}
$$
in the answer qubit. The <quantum phase kickback> identity gives
$$
O_x|s\rangle|-\rangle
=\frac1{\sqrt N}\sum_i(-1)^{x_i}|i\rangle|-\rangle.
$$
Choose a unitary $F$ with $F|0\rangle=|s\rangle$, apply $F^{-1}$ to the first register, and measure it. Its amplitude at $|0\rangle$ is
$$
\langle s|
\frac1{\sqrt N}\sum_i(-1)^{x_i}|i\rangle
=\frac1N\sum_i(-1)^{x_i}.
$$
This equals $+1$ or $-1$ for a constant string and zero for a balanced string. Thus outcome $0$ means constant, while every other outcome means balanced, with certainty after one oracle query. This is the <Deutsch-Jozsa test with an arbitrary uniform-state unitary>.
Back to article page
