7
$\begingroup$

Grover's algorithm is often described as a way to search a database in $O(\sqrt{N})$ time. For using it we need an oracle gate that represents some function $f$ such that $f^{-1}(1)$ is the answer. But how do you actually make such a “database oracle”?

Suppose I have an array of numbers $a$ that contains $w$ exactly once and I need to find $w$'s index. On a classical computer, I would load the array into memory and iterate through it until I find $w$.

For example, if $a = [3, 2, 0, 1, 2, 3]$ and $w = 0$, I expect to get 2 as the answer (or 3 in 1-indexing).

How do I represent this array in a quantum computer and make a gate that returns $a_x$ for some $x$?

In particular, do you need to have the entirety of the “database” within quantum memory (assuming there are some ways to access classical registers from quantum gates)?

$\endgroup$
  • $\begingroup$ @glS I think the answer explicitly says that the oracle might be not a database lookup but a hash function. I am interested in a case where you are given a concrete array and not a function. $\endgroup$ – Norrius Mar 28 '18 at 21:37
  • $\begingroup$ of what answer are you talking about? Whatever meaning you attach to it, at the end of the day the point is that the oracle implements $(-1)^{f(x)}$ for some function $f$. What do you mean with "you are given a concrete array and not a function"? $\endgroup$ – glS Mar 28 '18 at 21:53
  • $\begingroup$ @glS I was talking about the dupe you've suggested. I am curious about the details of that $f$ if all I want is compare it with some $w$. $\endgroup$ – Norrius Mar 28 '18 at 21:57
  • 2
    $\begingroup$ Possible duplicate of How is the oracle in Grover's search algorithm implemented? $\endgroup$ – Norbert Schuch Apr 2 '18 at 8:36
  • $\begingroup$ @NorbertSchuch The same dupe target again? $\endgroup$ – Norrius Apr 2 '18 at 10:54
6
$\begingroup$

$\newcommand{\xtarget}{\boldsymbol{x}_{\operatorname{target}}}\newcommand{\bs}[1]{{\boldsymbol #1}}\newcommand{\on}[1]{{\operatorname{#1}}}$No, it does not.

The "oracle" in Grover's algorithm is a function that, given any element $\boldsymbol x_k$, checks whether $\boldsymbol x_k$ is the element we are looking for, say $\xtarget$. To do this, the oracle does not need any knowledge of all the other elements $x_j$ that are in the database.

It may help to consider a more concrete example. Say you have a database of $20000$ four-digit phone numbers, with $\boldsymbol x_k$ denoting the $k$-th element in this database. You are interested in knowing what position in the database corresponds to the element $1234$. Let us assume that the element 10000 of the database is the only such element, that is, $\bs x_{10000}=1234$ and $\bs x_k\neq 1234$ for all $k\neq10000$.

In the classical case, being the database unsorted, there is no better way than going through every single element in the database, checking each one against the target $1234$. To do this, you only require to have an algorithm that, given $\bs x_k$, returns $\on{yes}$ if $\bs x_k=1234$ and $\on{no}$ otherwise. An equivalent way to state this problem is to say that we want an algorithm which, given a list of pairs $\{(k,\bs x_k)\}_{k=1}^{20000}$, returns the pair such that $\bs x_k$ is what we want. Thus, in our case, we want an algorithm which given $\{(k,\bs x_k)\}_{k=1}^{20000}$ returns $(10000,\bs x_{10000}=1234)$. Note that this means that the function checking each pair only checks for features of a part of the state, namely, the $\bs x_k$ part. Indeed, if this was not the case, the whole thing would be pointless because we wouldn't be recovering any information.

This last framing of the problem is the one that one should keep in mind while thinking about Grover's algorithm.

In the quantum case, the pairs $(k, \bs x_k)$ become the quantum states $|\psi_k\rangle$ (or just $|k\rangle$ how they are usually denoted), and the oracular function only checks that part of the information stored in $|\psi_k\rangle$ matches the target. The output of the procedure is the state $|\psi_{10000}\rangle$. Now, part of this state we already know, because it was hardcoded in the oracle: we know that the second part of the information encoded in $|\psi_{10000}\rangle$ is $1234$, because that is what we were looking for in the first place, and is the information that was encoded into the oracle itself. However, the state $|\psi_{10000}\rangle$ also carries additional information, namely the position in the database: $10000$. This information was not used to build the oracle, and is the information that we gain by running the algorithm.

Finally, note that the oracle knows nothing about the content of the full database. It only implements coherently a function that checks a single state $|\psi_k\rangle$ against its target. However, the fact that this gate works coherently means that one can input to this checker function a superposition of many (possibly all of the) elements of the database, and obtain an output which contains some global information about all the elements in the database.

$\endgroup$
0
$\begingroup$

You would build a function $f$ such that $f(x)$ first accesses the $x$-th item of your array and then compares it to $w$. An actual implementation might access the array encoded in extra (parameter) input qubits as if they were bits.

$\endgroup$
  • $\begingroup$ Is there a way to represent it in circuits or operator matrices or some other more concrete form? I am a little confused as to how you make it access a specific input. $\endgroup$ – Norrius Mar 28 '18 at 21:27
  • $\begingroup$ As the input is classical information (bits rather than qubits, just encoded as qubits), one can simply "copy" them with CNOTs. That's not a true copy but an entangled one, but that is good enough for this. It is important to uncompute the copy (again with CNOTs) or else Grover's algorithm won't work. $\endgroup$ – pyramids Mar 28 '18 at 21:30

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.