How does the induction step in the Grover-Rudolph scheme to prepare superpositions from probabilities work?

In https://arxiv.org/abs/quant-ph/0208112, the authors discuss a scheme to, given a discrete probability distribution $$\mathbf p\equiv (p_i)_i$$, under some assumptions on $$\mathbf p$$, prepare the superposition state $$|\psi(\mathbf p)\rangle = \sum_i \sqrt{p_i}|i\rangle.$$ The main step of the derivation seems to be the following: let $$N$$ be the number of elements in $$\mathbf p$$ (assuming I'm interpreting the paper correctly here), and $$n=\log N$$. Then

imagine the distribution is divided into some number $$2^m$$ of regions, and that we already have an $$m$$-qubit state $$|\psi_m\rangle = \sum_{i=0}^{2^m-1}\sqrt{p_i^{(m)}}|i\rangle.$$ [...] Here $$p_i^{(m)}$$ is the probability for the random variable $$x$$ to lie in the region $$i$$.

They then argue that from this state one can "add a qubit" and achieve the evolution $$\sqrt{p_i^{(m)}}|i\rangle\to |i\rangle(\sqrt{\alpha_i} |0\rangle+\sqrt{\beta_i}|1\rangle),$$ where $$\alpha_i,\beta_i$$ are the probabilities for $$x$$ to lie in the left and right half of region $$i$$.

I'm failing to get the gist of this notation. What's a simple toy example to understand what is going on here?

• – glS
Aug 10 at 14:24

Consider as a toy example a discrete distribution with four outcomes $$p_0,p_1,p_2,p_3$$.

Start from $$m=0$$, which means $$i=0$$, and $$|\psi_0\rangle=|0\rangle$$. The state for $$m=1$$ would instead be $$|\psi_1\rangle=\sqrt{p_0+p_1}|0\rangle+\sqrt{p_2+p_3}|1\rangle,$$ and finally for $$m=2$$ we'd get the target superposition $$|\psi_2\rangle=\sqrt{p_0}|0\rangle+\sqrt{p_1}|1\rangle+\sqrt{p_2}|2\rangle+\sqrt{p_3}|3\rangle.$$

To go from one step to the other, the evolution mentioned in the quote would be, at the $$m=0$$ step, $$|0\rangle \to |0\rangle(\sqrt{p_0+p_1}|0\rangle+\sqrt{p_2+p_3}|1\rangle),$$ because $$\alpha_0,\beta_0$$ would be the sum of the probabilities of the left and right half of the full interval. In practice, the sum of the first and last half of the probabilities.

In the $$m=1$$ step, the evolution would instead look like $$\sqrt{p_0+p_1}|0\rangle \to |0\rangle(\sqrt{p_0}|0\rangle+\sqrt{p_1}|1\rangle), \\ \sqrt{p_2+p_3}|1\rangle \to |1\rangle(\sqrt{p_2}|0\rangle+\sqrt{p_3}|1\rangle).$$ If we can implement both these evolutions it's clear we go from $$|0\rangle$$ to the target superposition.

As an addendum, let's consider how this evolution is performed.

Again, start at $$m=0$$ with $$|\psi_0\rangle=|0\rangle$$. The recipe, specialising the notation in the paper to our example, is to first implement the evolution $$|0\rangle\to |0\rangle |\theta_0\rangle, \qquad \theta_0\equiv\arccos\left(\frac{p_0+p_1}{1}\right) \equiv \arccos(p_0+p_1),$$ and then rotate another qubit conditionally to $$|\theta_0\rangle$$, that is, $$|\theta_0\rangle \to |\theta_0\rangle(\cos(\theta_0)|0\rangle+\sin(\theta_0)|1\rangle) = |\theta_0\rangle (\sqrt{p_0+p_1} |0\rangle+\sqrt{p_2+p_3}|1\rangle).$$

In the next iteration, you'd start with for example $$\sqrt{p_0+p_1}|0\rangle$$. Work out $$f(0)=p_0/(p_0+p_1)$$ and $$f(1)=p_3/(p_3+p_4)$$, which are used to define $$\theta_0\equiv \arccos\sqrt{f(0)}$$ and $$\theta_1\equiv\arccos\sqrt{f(1)}$$, and separately implement the evolutions (I'm writing both of the above steps in one line here): $$|0\rangle \to |0\rangle|\theta_0\rangle\to |0\rangle|\theta_0\rangle\left(\sqrt{f(0)}|0\rangle+\sqrt{1-f(0)}|1\rangle\right) = |0\rangle|\theta_0\rangle\left(\sqrt{\frac{p_0}{p_0+p_1}}|0\rangle+\sqrt{\frac{p_1}{p_0+p_1}}|1\rangle\right),$$ or equivalently, $$\sqrt{p_0+p_1} |0\rangle \to |0\rangle|\theta_0\rangle(\sqrt{p_0}|0\rangle+\sqrt{p_1}|1\rangle),$$ which is what we wanted. A completely analogous procedure gives $$\sqrt{p_2+p_3} |1\rangle \to |1\rangle|\theta_1\rangle(\sqrt{p_3}|0\rangle+\sqrt{p_4}|1\rangle).$$

The main assumption required for this procedure to be doable, is that the functions $$f(i)$$ must be efficiently computable classically.

This procedure clearly looks very similar to the one discussed in Preparing a quantum state from a classical probability distribution, or at least some of the underlying ideas are. They might operate under different resource assumptions though.

• Thanks for asking this! I’ll be honest that’s a famous paper that I’ve shamelessly used for example in answers here, but that I don’t yet fully understand. Aug 8 at 11:54
• To be clear, we’d have to use something like Quantum Circuits for Arithmetic arxiv.org/abs/1805.12445 for the $\arccos$, right? Aug 9 at 11:45
• my understanding is that the authors simply meant that these functions are efficiently computable classically, and therefore one could just use the classical circuit itself (made reversible as usual). Tbh, it feels to me like this scheme really just amounts to saying: you can always evolve $|i\rangle\to\sqrt{p_i}|0\rangle+\sqrt{1-p_i}|1\rangle$ as long as $p_i$ are efficiently computable. Via controlled-rotation trick, or really with any other unitary you can build. You then just do it iteratively to get more general superposition. I don't see this scheme as being really about probabilities
– glS
Aug 9 at 16:10