Loading a probability distribution (uniformly controlled rotations)

The target state for probabilities $p_0, \ldots, p_{2^n-1}$ is

$|\psi\rangle = \sum_{x=0}^{2^n-1} \sqrt{p_x}\,|x\rangle .$

Bisection. Grover and Rudolph build such a state one qubit at a time. With $m$ qubits holding a coarse version of the distribution over $2^m$ regions, one more qubit splits each region $i$ into its left and right halves: a rotation controlled on $i$ takes the new qubit to $\cos\theta_i|0\rangle + \sin\theta_i|1\rangle$, with $\theta_i = \arccos\sqrt{f(i)}$, where $f(i)$ is the probability of the left half given region $i$. Repeated until $m = n$, this gives $|\psi\rangle$. Their interest is the case where $f(i)$ comes from integrals of the density that an efficient classical algorithm can compute: they compute $\theta_i$ into an ancilla register, run the rotation, and uncompute. They state no gate count.

Möttönen et al.'s circuit. When the probabilities are simply a list, the angles can be computed in advance instead. The rotation on each new qubit then needs one angle for every setting of the qubits already placed, which is a uniformly controlled rotation. Möttönen, Vartiainen, Bergholm and Salomaa build a $k$-fold uniformly controlled rotation from $2^k$ rotations and $2^k$ CNOTs, with the angles in closed form. Their circuit takes an arbitrary state to $|0\ldots0\rangle$: $z$-rotations first equalise the phases, then $y$-rotations fold the magnitudes, with angles

$\alpha^{y}_{j,k} = 2\arcsin\!\left(\sqrt{\textstyle\sum_{l=1}^{2^{k-1}}|a_{(2j-1)2^{k-1}+l}|^2}\;\Big/\;\sqrt{\textstyle\sum_{l=1}^{2^{k}}|a_{(j-1)2^{k}+l}|^2}\right).$

Run backwards, the same circuit loads the state. For probabilities every amplitude $\sqrt{p_x}$ is real and non-negative, so every phase is zero and so is every $z$-angle. Only the $y$-rotations are left.

Cost. For turning one arbitrary state into another the paper gives $2^{n+2} - 4n - 4$ CNOTs and $2^{n+2} - 5$ rotations, and says only half the gates are needed when one end is a basis vector. The $y$-rotations alone, for a list of probabilities, come to $2^n - 2$ CNOTs and $2^n - 1$ RY rotations by the paper's own per-gate count; the paper does not state that figure. Either way the count grows with $2^n$, and that is not an artefact of this circuit: counting degrees of freedom, the same paper finds that an arbitrary complex state needs at least $\lceil\tfrac14(2^{n+1} - 3n - 2)\rceil$ CNOTs. Cheaper loading needs structure in the target, such as few nonzero entries, or a smooth function whose matrix product state has small bond dimension; both have their own Atlas entries. Grover and Rudolph's case needs the integrals of the density, and the Atlas entry for their method records what obtaining those integrals costs.

The worked example. Binomial$(7, \tfrac12)$ on 3 qubits, $p_x = \binom{7}{x}/128$. The first split is exactly one half, so the first rotation is $R_y(\pi/2)$. The second level uses two angles and the third uses four. The check compares all eight outcome probabilities with $\binom{7}{x}/128$.