Preparing a quantum state from a classical probability distribution

Question

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$.

Remarks: My question could be seen as how one 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?

Answer 1

Suppose we have two quantum circuits, the first one $S$ computes (or at least approximates) the classical squareroot function ($\sqrt{\cdot}$) via $$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 via $$A|x\rangle|0\rangle=|x\rangle |\arccos(x)\rangle.$$ Lastly, suppose we have are able to preform controlled single qubit rotations $R$ (or at least approximately preform these) in the following sense $$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 extra 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 in this form it is clear that the amplitude amplification algorithm can output the state $|p\rangle$ in $\Theta(\sqrt{n})$ queries with high probability.