Suppose we have an oracle $O_f$ that given an initial state $|x\rangle$ maps it into the following state:
$$
O_f : |x\rangle \mapsto e^{if(x)} |x\rangle
$$
Now, assuming that $f(x) \in [0,1]$, is it possible to construct a quantum circuit $O_p$ such that:
$$
O_p : |x\rangle \otimes |0\rangle \mapsto |x\rangle \otimes (\sqrt{f(x)} |0\rangle + \sqrt{1-f(x)} |1\rangle)
$$
using $O_f$ ? If you can suggest some references, i would appreciate it. Thank you very much.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ It should be possible see exercise 8.3.2 in Kaye, Mosca, and LaFlamme's "An introduction to quantum computing". $\endgroup$– CondoMay 21, 2020 at 19:04
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
As a bare minimum, you would need access to a controlled version of your oracle. This cannot be created from the oracle itself (I'm sure there's already an SE question about this part, but cannot immediately lay my hands on it).
A typical construction would allow you to create (Hadamard - controlled oracle - Hadamard) would create an output $$ \cos\frac{f(x)}{2}|0\rangle+i\sin\frac{f(x)}{2}|1\rangle, $$ which is obviously not what you're asking for. There might be some simple modifications that let you approximate what you're after.
To get what you're actually asking for, I suspect you have to do some quite sophisticated stuff. Essentially, perform phase estimation to estimate the value of $f(x)$ onto a second register, and use that register as a control to produce the state you want, with an accuracy defined by the size of the register.
answered Mar 9, 2020 at 10:55
-
$\begingroup$ Is it clear that you cannot do it without a controlled version of the oracle? $\endgroup$– smapersMar 9, 2020 at 10:57
-
$\begingroup$ @smapers The problem is that if it acts on $|x\rangle$, it's only ever a global phase, which cannot have any observable influence. You need to be able to access it in superposition, which means a controlled-oracle with the control in superposition (since the target has to be the state $|x\rangle$). $\endgroup$ Mar 9, 2020 at 10:59
-
-
$\begingroup$ @DaftWullie, first of all, thank you very much for your answer. The whole point of this question is because i want to avoid phase estimation, due to the extensive use of powers of the control unitaries C-U ,fourier transform and the probabilistic nature of the algorithm. I think that the controlled version of the oracle is not a problem, however producing $\sqrt{f(x)}$ is quite challenging, if possible at all. $\endgroup$– As10Mar 9, 2020 at 11:09
-
$\begingroup$ Well, my intuition, at least, suggests that you can't. What you can reasonably get at is some linear function of $e^{if(x)}$. The amplitudes you're asking for require a high-order expansion to get any reasonable accuracy, so you'd need to extensively use high powers of c-U. $\endgroup$ Mar 9, 2020 at 11:17
$\begingroup$
$\endgroup$
Given controlled access to the phase oracle, this is possible with surprisingly small overhead by avoiding phase estimation altogether. The technique you are after relies on applying "quantum singular value transformations" to objects that are known as "block encodings", and it was invented by Gilyén et al. in 2018. The idea was originally introduced in this paper, Appendix B, which builds on techniques from this paper. Alternatively, you can have a look at this master's thesis, Circuit 6.2.5.
It appears that there is a slight error in the statement of the latter reference, as the action of $Q_f$ in the box referred to should actually be:
$$Q_f : |x\rangle \otimes |0\rangle^{\otimes 3} \mapsto |x\rangle \otimes \left(\sqrt{\frac12 + \frac14f(x)}|0\rangle^{\otimes 3} + \sqrt{\frac12 - \frac14f(x)}|\psi(x)\rangle|1\rangle\right).$$
Similarly, the action of $Q_2$ further down in the box should be:
$$Q_2 : |0\rangle^{\otimes 3} \otimes |x\rangle \mapsto \left(\frac12\sqrt{\frac12 + \frac14f(x)}|0\rangle^{\otimes 3} + \sqrt{\frac78 - \frac{1}{16}f(x)}|1\rangle|\phi(x)\rangle\right)|x\rangle.$$
All the rest should be correct as stated.
Keep in mind that the operation you wish to implement, i.e., the probability oracle of $f$, makes little sense whenever $f$ takes negative values. Moreover, the square root that appears in the probability oracle behaves erratically close to $0$, so it makes sense to assume that the function values of $f$ are bounded away from $0$. Gilyén et al. overcome this by assuming that the values of $f$ are contained in $(\delta,1-\delta)$. The latter reference essentially does the same thing, but overcomes it by assuming that $|f| \leq 1/2$ and implementing the probability oracle of $\frac12 + \frac14f(x)$.
As a final remark, note that the conversion you are after up to norm error $\varepsilon$ takes $O(\log(1/\varepsilon)^2)$ queries to the phase oracle, which is surprisingly little compared to the number of queries $O(1/\varepsilon)$ you would need if you used phase estimation as an intermediate step. An explanation can be given along the following lines: phase estimation gives you a binary representation of the function value $f(x)$, which you subsequently postprocess to implement the probability oracle. This is a difficult task, as it requires learning the value of $f(x)$ in the process (as you could measure after phase estimation to get a binary value of $f(x)$). The new techniques circumvent writing down such a binary representation of $f(x)$. This is why I like to call the new technique an instance of analog computation, and I refer to subroutines that give you binary representations, like phase estimation, as instances of digital computation.
