The ratio $f_i=A_i/B_i$ is the conditional probability that $X$ lies in the left half of interval $i$. After the controlled rotation and uncomputation of $|\theta_i\rangle$, append the rotation qubit to the interval label. The amplitudes become
$$
\sqrt{p_i^{(m)}f_i},|i0\rangle
+\sqrt{p_i^{(m)}(1-f_i)},|i1\rangle.
$$
But
$$
p_i^{(m)}f_i=p_{2i}^{(m+1)},
\qquad
p_i^{(m)}(1-f_i)=p_{2i+1}^{(m+1)}.
$$
Consequently one refinement step maps
$$
|\psi_m\rangle\longmapsto|\psi_{m+1}\rangle.
$$
Starting from $|\psi_1\rangle$ and repeating this <hierarchical probability-distribution state preparation> for $m=1,\ldots,n-1$ gives
$$
\boxed{|\psi_n\rangle
=\sum_{j=0}^{2^n-1}\sqrt{p_j^{(n)}}|j\rangle}.
$$
There are $n-1=O(\log N)$ refinement levels, each of polylogarithmic size by assumption.

Solution

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

 Solution

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