= Solution
Implement the assumed efficient classical algorithm for $x\mapsto\theta_x$ as a <reversible circuit>. On input $|x\rangle|0^s\rangle$, it computes an $O(m)$-bit <binary expansion> of the angle in a work register using $\operatorname{poly}(m)$ <Toffoli gates> and elementary reversible gates. Write the computed angle as a sum of binary-weighted angles. For each angle bit, apply the corresponding controlled single-qubit $R_y$ rotation to the target. These rotations have the same axis, so their angles add and produce
$$
|x\rangle|\widetilde\theta_x\rangle
(\cos\theta_x|0\rangle+\sin\theta_x|1\rangle).
$$
Finally apply <uncomputation> to erase the work register. Each <Toffoli gate> and controlled rotation has a constant-size decomposition into one- and two-qubit gates when arbitrary one-qubit rotations are available. Ignoring the stipulated precision costs, the resulting circuit has size $\operatorname{poly}(m)$ and returns every <quantum ancilla> to zero.
Back to article page
