Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 324 / 2 / c / i / Solution

Use reversible quantum arithmetic on an ancillary work register. On each computational-basis branch, computewhereBecause the classical algorithms for $A_i$ and $B_i$ are efficient, they can be made reversible with polynomial overhead. Reversible division, square root, and inverse cosine to the retained binary precision likewise use $\mathrm{poly}(\log N)$ gates under the question's precision convention. Uncompute the $A_i$ and $B_i$ work registers, leaving