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?

  • 3
    $\begingroup$ does this help? $\endgroup$ – Mark S May 20 '20 at 22:24
  • $\begingroup$ the answers here may also be of some use quantumcomputing.stackexchange.com/questions/11347/… $\endgroup$ – Sam Palmer May 21 '20 at 1:26
  • $\begingroup$ @MarkS yes this looks promising, thanks! $\endgroup$ – Condo May 21 '20 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 '20 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 '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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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