# Preparing a quantum state from a classical probability distribution

Suppose I have a black-box unitary $$U_p$$ which is described as follows: given a finite probability distribution $$p:\{1,\ldots,n\}\rightarrow \mathbb{R}_{\geq0}$$, where $$\sum_{x=1}^n p(x)=1$$, the action of the black box on a basis is given by $$U_p:|x\rangle|0\rangle\mapsto |x\rangle |p(x)\rangle,$$ where I am assuming I can encode each $$p(x)$$ into some register of quantum states (say using binary encoding into qubits). Then applying $$U_p$$ to a superposition of inputs is easy and I can easily construct a circuit that prepares the state $$\frac{1}{\sqrt{n}}\sum_{x=1}^n |x\rangle |p(x)\rangle.$$ My question is the following, using what I have described above or otherwise how could I prepare the quantum state $$|p\rangle:=\sum_{x=1}^n \sqrt{p(x)}|x\rangle$$ given access to $$U_p$$. I guess my question could be see as how can make this fit into the amplitude amplification scheme.

One can see that this is a generalization of the typical quantum search, since if $$p(x)=\delta_{x,y}$$ (the distribution that is $$1$$ if $$x=y$$ and 0 if $$x\neq y$$) then $$U_p$$ is the quantum black-box for one marked item quantum search, and therefore preparing the state $$|y\rangle$$ can be done with $$\Theta(\sqrt{n})$$ queries to $$U_{\delta(x,y)}$$.

Update: I think this might boil down to someone explaining how I might implement the relative-phase like transformation $$V:|x\rangle|f(x)\rangle\mapsto |x\rangle \big(\sqrt{\tfrac{f(x)}{2^m}}|0\rangle+\sqrt{1-\tfrac{f(x)}{2^m}}|1\rangle\big)$$ using some sort of controlled rotation?

• does this help? – Mark S May 20 '20 at 22:24
• the answers here may also be of some use quantumcomputing.stackexchange.com/questions/11347/… – Sam Palmer May 21 '20 at 1:26
• @MarkS yes this looks promising, thanks! – Condo May 21 '20 at 13:33
• see my update, I think I can see how to proceed if I could preform such a transformation $V$. – Condo May 21 '20 at 14:21
• the controlled rotations are a horrible (disclaimer I have research them, but have not implemented as of yet) I would dig into the Quantum monte carlo literature as this type of rotation plays a crucial part. I would start here dx.doi.org/10.1098/rspa.2015.0301 if you look at pg. 8 – Sam Palmer May 21 '20 at 16:52

Suppose we have two quantum circuits, the first computes (or at least approximates) the classical $$\sqrt{\cdot}$$ function $$S|x\rangle|0\rangle=|x\rangle |\sqrt{x}\rangle,$$ while the second circuit $$A$$ computes (again could probably just approximate) the $$\arccos(\cdot)$$ function $$A|x\rangle|0\rangle=|x\rangle |\arccos(x)\rangle.$$ Lastly, suppose we have are able to preform controlled single qubit rotation (or at least approximately preform these) $$R|\theta\rangle|0\rangle=|\theta\rangle(\cos(\theta)|0\rangle+\sin(\theta)|1\rangle).$$
Then using the oracle $$U_p|x\rangle|0\rangle=|x\rangle|p(x)\rangle,$$ along with a bunch of auxiliary qubits (which I won't write out in detail) we can create a circuit $$C$$ which computes (or at least approximates) the state $$C|x\rangle|0\rangle \mapsto |x\rangle(\cos(\arccos(\sqrt{p(x)})|0\rangle+\sin(\arccos(\sqrt{p(x)})|1\rangle)\\=|x\rangle(\sqrt{p(x)})|0\rangle+\sqrt{1-p(x)})|1\rangle).$$ Now, using $$\log(n)$$ qubits we can create the superposition $$\frac{1}{\sqrt{n}}\sum_{x=1}^n |x\rangle$$ using Hadamards. Applying $$C$$ to this superposition we can create the state $$\frac{1}{\sqrt{n}}\sum_{x=1}^n(\sqrt{p(x)})|0\rangle+\sqrt{1-p(x)})|1\rangle)|x\rangle.$$ If we rewrite this state as $$\frac{1}{\sqrt{n}}(\sum_{x=1}^n\sqrt{p(x)}|x\rangle)|0\rangle+\frac{1}{\sqrt{n}}(\sum_{x=1}^n\sqrt{1-p(x)}|x\rangle)|1\rangle\\ =\sqrt{\tfrac{1}{n}}|p\rangle|0\rangle+\sqrt{\tfrac{n-1}{n}}|\tilde{p}\rangle|1\rangle.$$ Then it is clear that the amplitude amplification algorithm will output the state $$|p\rangle$$ in $$\Theta(\sqrt{n})$$ queries with high probability.