Use reversible quantum arithmetic on an ancillary work register. On each computational-basis branch, compute

∣ i ⟩ ∣0 ⟩ ∣0 ⟩ ⟼ ∣ i ⟩ ∣ A_{i} ⟩ ∣ B_{i} ⟩ ⟼ ∣ i ⟩ ∣ A_{i} ⟩ ∣ B_{i} ⟩ ∣ θ_{i} ⟩,

where

f_{i} = \frac{A _{i}}{B _{i}}, θ_{i} = arccos f_{i} .

(2)

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

poly (lo g N)

gates under the question's precision convention. Uncompute the

A_{i}

and

B_{i}

work registers, leaving

∣ ψ_{m} ⟩ = i = 0 \sum 2^{m} - 1 p_{i}^{(m)} ∣ i ⟩ ∣ θ_{i} ⟩ .

(3)

Solution

 0  0

Suppose the angle register stores a fixed-point expansion

θ_{i} = \sum_{r = 1}^{q} θ_{i r} 2^{- r} θ_{m a x}

. Append a target qubit in

∣0 ⟩

. For each angle bit

h e t a_{i r}

, apply to the target a controlled

R_{y} (2^{1 - r} θ_{m a x})

. Rotations about the same axis commute, so their product is

R_{y} (2 θ_{i})

and

∣0 ⟩ ⟼ cos θ_{i} ∣0 ⟩ + sin θ_{i} ∣1 ⟩ .

(1)

With

q = O (poly lo g N)

retained bits, each controlled rotation decomposes into one- and two-qubit gates and the complete quantum variable rotation has polylogarithmic size. Thus the required branchwise map is implemented coherently for every