= Solution
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}.
$$
Back to article page
