= Solution
Write the promised phase as $\phi=2\pi m/8$. Prepare three logical <qubits> in $|+\rangle$ and attach zero ancillas in three blocks of sizes four, two and one. A block of size $r$ is prepared by fanout <CNOT gates> as
$$
\frac{|0^r\rangle+|1^r\rangle}{\sqrt2}.
$$
Apply one copy of $U_\phi$ to every physical <qubit> in every block, all in the same time step. Undo each fanout. The logical block output is $(|0\rangle+e^{ir\phi}|1\rangle)/\sqrt2$ and every ancillary wire returns to zero. This is <parallel phase multiplication by coherent fanout>; its intermediate <entanglement> copies basis labels, and does not clone an arbitrary <quantum state>.
For block weights $4,2,1$, the three logical wires now contain
$$
\bigotimes_{r\in(4,2,1)}\frac{|0\rangle+e^{ir\phi}|1\rangle}{\sqrt2}
=\frac1{\sqrt8}\sum_{l=0}^7e^{i\phi l}|l\rangle.
$$
Apply the specified negative-sign <quantum Fourier transform> and measure. Part (a) gives label $m$ deterministically. Thus \b[seven parallel phase-gate applications, on three logical wires and four ancillas, identify the phase in one oracle time step]. Preparation, uncomputation and the Fourier transform cost no time under the stated model; using serial powers would not meet the time requirement.
Back to article page
