= Solution
Label the control <qubits> by binary weight: the bit $x_n$ contributes $2^n$ to $x=\sum_{n=0}^{N-1}2^nx_n$. For each $n$, use that <qubit> as the control of the supplied controlled-$V^{2^n}$, with the same target <eigenstate> $|v_j\rangle$. The <controlled unitary gate> acts by
$$
\frac{|0\rangle+|1\rangle}{\sqrt2}|v_j\rangle\longmapsto\frac{|0\rangle+e^{i2^n\phi_j}|1\rangle}{\sqrt2}|v_j\rangle,
$$
since $V^{2^n}|v_j\rangle=e^{i2^n\phi_j}|v_j\rangle$. The target remains unchanged after every application. Multiplying these factors gives
$$
\left[\bigotimes_{n=0}^{N-1}\frac{|0\rangle+e^{i2^n\phi_j}|1\rangle}{\sqrt2}\right]|v_j\rangle=\boxed{\frac1{\sqrt{2^N}}\sum_{x=0}^{2^N-1}e^{i\phi_jx}|x\rangle}\,|v_j\rangle.
$$
The ordering of the tensor factors is chosen to match the binary place values. Discarding the unchanged target leaves the required phase register. This uses <quantum phase kickback> in the phase accumulation step of <quantum phase estimation>.
Back to article page
