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?

  • 4
    $\begingroup$ does this help? $\endgroup$ May 20, 2020 at 22:24
  • $\begingroup$ the answers here may also be of some use quantumcomputing.stackexchange.com/questions/11347/… $\endgroup$
    – Sam Palmer
    May 21, 2020 at 1:26
  • $\begingroup$ @MarkS yes this looks promising, thanks! $\endgroup$
    – Condo
    May 21, 2020 at 13:33
  • 1
    $\begingroup$ see my update, I think I can see how to proceed if I could preform such a transformation $V$. $\endgroup$
    – Condo
    May 21, 2020 at 14:21
  • $\begingroup$ 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 $\endgroup$
    – Sam Palmer
    May 21, 2020 at 16:52

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.