4
$\begingroup$

I have been trying to implement methods from paper Creating superpositions that correspond to efficiently integrable probability distributions by Grover and Rudolph.

It is stated that there exists an efficient (polynomial) process for the preparation of certain probability density functions (e.g. log-concave distributions).

Specifically, in equation 5. It is stated that

$$\sqrt{p_i^{(m)}}|i\rangle |0...0\rangle \rightarrow \sqrt{p_i^{(m)}}|i\rangle |\theta_i\rangle$$

Can be done efficiently under these assumptions.

I have not found any details on how this can actully be done, either with and example or with the details of how such an efficient circuit could be composed.

Would highly appreciate any insights on this.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I think it's because it's a purely classical operation. You can use regular logic to read the value of the first register and output the state $\theta_i$ on the second register, assuming you know classically $\theta_i$ (i.e. $f(i)$ here). $\endgroup$
    – glS ♦
    Commented Jul 26, 2020 at 18:51
  • $\begingroup$ @glS , Thanks for this 👍👍 $\endgroup$
    – Amir Naveh
    Commented Jul 27, 2020 at 5:51
  • $\begingroup$ Lets indeed assume that θi is easy to known. My understanding is that now we wish to put this value in the register. How can this be done efficiently? Is there an easy way to load a value into a register? $\endgroup$
    – Amir Naveh
    Commented Jul 27, 2020 at 5:59
  • 5
    $\begingroup$ Does this answer your question? Preparing a quantum state from a classical probability distribution $\endgroup$
    – Condo
    Commented Aug 5, 2020 at 16:01
  • 1
    $\begingroup$ Aren't there too many such $\theta_i $ (namely $2^n$) to compute? Doesn't that ruin the speedup? $\endgroup$
    – Hayk Tepanyan
    Commented May 15, 2022 at 7:57

1 Answer 1

Reset to default
0
$\begingroup$

I think now I get @gls's point: since basic classical arithmetics (like addition, multiplication, etc.) can be done quantumly and it's assumed that the $i$ -> $\theta_i$ can be done easily classically then it should be possible to do quantumly as well. The trick is that in the quantum circuit we get the benefit of calculating $2^m$ many $\theta_i$s in step $m$, since we have that many $i$s in superposition.

As for an example, following the notations from Creating superpositions that correspond to efficiently integrable probability distributions by Grover and Rudolph, the $i$ -> $\theta_i$ transformation for the uniform distribution will be something like

$f(i) = \frac{\int_a^b p(x)dx}{\int_a^{2b} p(x)dx} = \frac{1}{2} $

$\theta_i=arccos(\sqrt{f(i)})=0.785$

so all you need is a unitary that does $| i\rangle |0 \rangle $ -> $| i\rangle |0.785 \rangle$ which can be done easily.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What exactly is f(i) in this context? why is it defined as a fraction of integrals? $\endgroup$
    – consthatza
    Commented Jun 4, 2022 at 5:54
  • $\begingroup$ Updated the answer. $\endgroup$
    – Hayk Tepanyan
    Commented Jun 5, 2022 at 6:07

Your Answer

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

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