# What's an example of a superposition $\sum_i \sqrt{p_i}|i\rangle$ that cannot be prepared efficiently?

As also discussed in (How does the induction step in the Grover-Rudolph scheme to prepare superpositions from probabilities work? and How does the uncomputation step work in the Grover-Rudolph scheme to prepare $\sum_i\sqrt{p_i}|i\rangle$?), the Grover-Rudolph scheme (https://arxiv.org/abs/quant-ph/0208112) is used to prepare an $$n$$-qubit superposition $$\sum_{i=0}^{2^n-1} \sqrt{p_i}|i\rangle$$ via an iterative procedure.

Each step of the procedure involves taking a superposition (possibly obtained from the previous iteration) of the form $$\sum_{i=0}^{2^m-1}\sqrt{p_i'}|i\rangle$$ for some $$0\le m, with $$p_i'$$ denoting some "coarse-graining" of the final target distribution, and implementing an evolution such that each $$\sqrt{p_i'} |i\rangle$$ evolves into some $$|i\rangle(\sqrt{p_i''}|0\rangle+\sqrt{1-p_i''}|1\rangle)$$ for a suitable "refinement" $$p_i''$$. See the links above for an example of what this means in practice for $$n=2$$.

Each refinement step works adding an ancilla containing an angle $$\theta_i$$, then performing a controlled operation conditioned on this angle, and finally uncomputing the ancilla with $$\theta_i$$.

The main claim of the paper is that such superpositions can be prepared efficiently as long as the underlying distribution is "efficiently integrable". This requirement comes, as far as I can tell, from the step where we write into the ancilla the angles $$\theta_i$$. These angles contain in practice sums of probabilities, hence why we mind about "integrability". More precisely, following the paper's notation, $$\theta_i=\arccos\sqrt{f(i)}$$ where $$f(i) = \frac{\int_{x^i_L}^{\frac{x^i_R-x^i_L}{2}} dx \,p(x)}{\int_{x^i_L}^{x^i_R} dx \,p(x)}.$$ Without delving into what the symbols in this last expression mean exactly, the gist (as I understand it) is that $$f(i)$$ is a ratio between the sum of a subset of probabilities, over the sum of a larger number of probabilities. For example if we want to go from $$\sqrt{p_0+p_1}|0\rangle+\sqrt{p_2+p_3}|1\rangle$$, we'll get $$f(0)=p_0/(p_0+p_1)$$ and $$f(1)=p_2/(p_2+p_3)$$. They're just the angles we need to get the correct amplitudes in the next iteration.

What are example situations where we cannot efficiently prepare a given target distribution? I have a hard time thinking of examples of "not efficiently integrable distribution", because here we're talking discrete distributions, so "integrability" is just about summing subsets of probabilities, and given that one presumably knows the probabilities $$p_i$$, how would you not be able to efficiently compute their sums?

From the paper's introduction, I'm guessing the authors might have been thinking about a different type of problem, where "efficient integrability" is an issue, or maybe where you don't know a priori the probabilities $$p_i$$ you want in your amplitudes because they come from coarse-graining a continuous distribution. But I don't know enough about this context to come out with an explicit example of such a situation.

• Isn't the answer in Eq. (8) of the paper? Or take wiki "The following distributions are non-log-concave for all parameters: The Student's t-distribution. The Cauchy distribution. The Pareto distribution. The log-normal distribution. The F-distribution." Aug 10, 2023 at 18:07
• I like the above comment! And just to add a bit more context, there are also many states that are asymptotically efficient to implement using the Grover-Rudolph method but in practice require an unrealistically really large overhead. One example is the log-normal distribution in the context of finance (appendix B in quantum-journal.org/papers/q-2021-06-01-463) Aug 12, 2023 at 9:22
• @QuantumMechanic yes but "non-log-concave" is not an explicit example. And it's not at all clear to me why this particular feature is important, or better said, in what context it is. Taking as example eg eq (8), why would that particular state (for some values of $p_i$) not be efficiently preparable with the scheme? Ok, it's not log-concave, but so what? I can still compute easily the angles required for the controlled rotation at each step, no? In other words, another phrasing of this question could be: show explicitly where the preparation scheme fails for a non-log-concave distribution
– glS
Aug 13, 2023 at 10:26
• @gIS I think it's just that the classical part of computing what to prepare is not efficient - nothing to do with the quantum part of the problem Aug 13, 2023 at 14:20
• @QuantumMechanic if so, the way these results are usually stated is somewhat misleading IMO. The statement should be "any target superposition can be prepared efficiently". Unless the point is that there are distributions not efficiently computable classically (thus somehow defined implicitly) that nonetheless correspond to efficiently preparable states?
– glS
Aug 13, 2023 at 18:34