= Solution
Use a <reversible circuit> $T$ to compute an $L=O(n)$-bit representation of the angle into a workspace register, with all additional work bits retained:
$$
|x\rangle|0^L\rangle|0\rangle\xrightarrow{T}
|x\rangle|\theta_x\rangle|0\rangle.
$$
Write that representation as $\theta_x=\sum_{l=1}^L b_l(x)\alpha_l$, with known binary place values $\alpha_l$ (including the fixed scale and any integer bit). On the target, apply a <controlled unitary gate> $R_y(2\alpha_l)$ controlled by each angle bit $b_l$. Rotations about the same axis add their angles, so their product is
$$
\prod_{l=1}^LR_y(2b_l\alpha_l)=R_y(2\theta_x),\qquad
R_y(2\theta_x)|0\rangle=\cos\theta_x|0\rangle+\sin\theta_x|1\rangle.
$$
Finally apply $T^\dagger$ to perform <uncomputation>. The workspace returns to zero while the control register and rotated target remain unchanged; the construction works coherently on every superposition of $x$.
A <polynomial time> classical calculation has a polynomial-size <reversible circuit> with <Toffoli gates>, and each Toffoli gate has a constant-size decomposition into one-qubit and two-qubit gates. The $L$ controlled rotations are themselves two-qubit gates. Thus the total <quantum circuit> size is \b[$\operatorname{poly}(n)$]. This is the <binary-angle implementation of a quantum variable rotation>; the stipulated angle precision is understood.
Back to article page
