# Super-position for a given distribution Background - Recall conditional probability, specifically $\boxed{P(A)=P(A|B)P(B)}$ . - How to compute $arccos$ circuit that operated on qubits: by a reversible polynomial approximation of $\arccos$ using Horner rule in multiple steps: one bracket at a time. - How to Rotate controlled by a an angle which depends on qubits in the computational basis i.e., which representing a binary number? we need controlled rotation $CR_y$ which is implemented by $CR_y(\theta)=(I\otimes R_y(\theta/2))CNOT(I\otimes R_y(-\theta/2))CNOT$note that this is done on a single bit. For multiple bits $\sum_{i=0}^{n-1} b_i2^{-i}$ we can compute $CR_y$ one bit a time and then compose the rotations i.e., $C^{b_{n-1}}R_y(2^{-(n-1)})\circ\cdots\circ C^{b_1}R_y(2^{-1})\circ C^{b_0}R_y(2^0)= R_y(\sum_{i=0}^{n-1}b_i2^{-i})$ The paper [Creating superpositions that correspond to efficiently integrable probability distributions Lov Grover and Terry Rudolph](https://arxiv.org/pdf/quant-ph/0208112) propose a method for generating a superposition $\psi=\sum_{i=0}^{2^n-1}\sqrt{p_i}|i\rangle$ where the $p_i$ are approximation of the probability of the $i$-th interval when dividing the support in the x-axis of the cumulative-distribution-function (CDF) to $2^n$ equal intervals. the i-th interval is represented as binary number. The method require that the distribution can be computed efficiently using integral $\int_a^b p(x)dx$ . The general idea of the: it works in steps, it starts with single interval with probability 1. Each step the intervals are split by half and their binary label is extended with 0 and 1 as their LSB i.e., $|i\ll2\rangle$ and $|i\ll2+1\rangle$. The probability of right-half of $|i\rangle$ is changed to it's probability in the CDF and the same for the left-half. This is repeated until a superposition of $n$-qubits is reached. The probabilities are associated probabilities from the CDF. Let's assume we have computed the superposition of step-$m$ : $|\psi_m\rangle=\sum_{i=0}^{2^m-1}\sqrt p_i^{(m)}|i\rangle$ where $p_i^{(m)}$ is the probability of the i-th interval of step m i.e., $\int_{x^{(i)}_{m,L}}^{x^{(i)}_{m,R}}p(x)dx$ where $x^{(i)}_{m,L}$ is the value of the left boundary of the i-th interval of the m-step. We show how to compute $|\psi_{m+1}\rangle=\sum_{i=0}^{2^{m+1}-1}\sqrt{ p_i^{(m+1)}}|i\rangle$: define function $f$ for the left half probability using conditional probability i.e., what is the probability sampling from the left interval conditioned that we are in the i-th interval: $f(i)=\frac{\int_a^{(x^{(i)}_{L}+x^{(i)}_{R})/2} p(x)dx}{\int_{x^{(i)}_{L}}^{x^{(i)}_{R}}p(x)dx}$ and the right half probability is $1-f(i)$ . define $\theta_i:=\arccos\sqrt{f(i)}$ and produce a circuit for it that depends on $i$. pad $|\psi_m\rangle$ with ancilla of $|0...0\rangle$ and compute the circuit of $\theta_i$ over $|\psi_m\rangle|0\ldots0\rangle=\sum_{i=0}^{2^m-1}\sqrt{ p_i^{(m)}}|i\rangle|0\ldots0\rangle$ . The result $|\psi_m\rangle=\sum_{i=0}^{2^m-1}\sqrt{p_i^{(m)}}|i\rangle|\theta_i\rangle$ . note that computing $\arccos$ can be done by a reversible polynomial approximation of $\arccos$ using Horner rule and computing the CDF integral is given as an efficient circuit also depends on $|i\rangle$ and the step we are in. Now comes the magic for inflating the superposition: compute a rotation $R_y$ by angle of $2\theta_i$ i.e., $R_y(2\theta_i)=\begin{bmatrix} \cos(\theta_i) & -\sin(\theta_i) \\ \sin(\theta_i)& \cos(\theta_i)\end{bmatrix} $ which means that $ R_y(2\theta_i)|0\rangle=\cos(\theta_i)|0\rangle+\sin(\theta_i)|1\rangle=\sqrt{f(i)}|0\rangle+\sqrt{1-f(i)}|1\rangle$ . This is the most important step! when we rotate the zero ancilla we get a new superposition which is tensor-multiplied with the input qubits. This is how the superposition is extended! note that the unitarian matrix elements depend on the value in the m-qubits. This is implemented by controlled-rotation as explained in the background section. which is the conditioned probability of the right sub-interval. We get $ \begin{align} \sum_{i=0}^{2^m-1}\sqrt{p_i^{(m)}}|i\rangle\bigg(\sqrt{f(i)}|0\rangle+\sqrt{1-f(i)}|1\rangle\bigg)&=\sum_{i=0}^{2^m-1}\sqrt{p_i^{(m)}f(i)}\cdot|i\rangle|0\rangle+\sqrt{p_i^{(m)}(1-f(i))}|i\rangle|1\rangle\\ &= \sum_{i=0}^{2^m-1}\sqrt{p_i^{(m)}}|i\rangle|\theta_i\rangle \\ &=|\psi_m\rangle \end{align} $ note: $\sqrt{p_i^{(m)}f(i)}$ is multiplication of the probability of interval $i$ with the conditioned-probability of its left half and this internal which is qual to the probability of the half left not conditioned. And $p_i^{(m)}\cdot(1-f(i))$ is probability of the right half because it is the multiplication of the condition on the right of that interval: $1-f(i)=\frac{\int_{x^{(i)}_{L}}^{x^{(i)}_{R}}p(x)dx-\int_a^{(x^{(i)}_{L}+x^{(i)}_{R})/2} p(x)dx}{\int_{x^{(i)}_{L}}^{x^{(i)}_{R}}p(x)dx}$ Nice. note: this technique require $O(n)$ operations. Reference: [Creating superpositions that correspond to efficiently integrable probability distributions Lov Grover and Terry Rudolph](https://arxiv.org/pdf/quant-ph/0208112) by Lov Grover and Terry Rudolph ## Created 2026-03-18 11:54