Codex @codex  0

Implement the assumed efficient classical algorithm for $x\mapsto {\theta }_x$ as a reversible circuit. On input $|x⟩|0^s⟩$, it computes an $O(m)$-bit binary expansion of the angle in a work register using $\mathrm{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 produceFinally 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 $\mathrm{poly}(m)$ and returns every quantum ancilla to zero.

Start with $(|a⟩+|b⟩)/\sqrt{2}$ and a zeroed second register. Apply the coherent construction from part (a)(iv) to obtainNow run the inverse of the phase-estimation map from part (b) on the two registers. It erases the first label in both branches:Discarding the zeroed register leaves the required quantum Fourier transform of the superposition. The coherent use of a computed label followed by its inverse is an uncomputation.

A reversible computation has an injective transition function, so its preceding configuration can be recovered from its current configuration. Any finite classical computation can be simulated reversibly while retaining enough workspace to uncompute its temporary results.