Use reversible <quantum arithmetic> on an ancillary work register. On each computational-basis branch, compute
$$
|i\rangle|0\rangle|0\rangle
\longmapsto
|i\rangle|A_i\rangle|B_i\rangle
\longmapsto
|i\rangle|A_i\rangle|B_i\rangle|\theta_i\rangle,
$$
where
$$
f_i=\frac{A_i}{B_i},
\qquad
\theta_i=\arccos\sqrt{f_i}.
$$
Because 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 $\operatorname{poly}(\log N)$ gates under the question's precision convention. Uncompute the $A_i$ and $B_i$ work registers, leaving
$$
\boxed{
|\widetilde\psi_m\rangle
=\sum_{i=0}^{2^m-1}\sqrt{p_i^{(m)}}|i\rangle|\theta_i\rangle}.
$$

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/iii/paper-324/2/c/i/solution