Grover Iteration

Question

I have two questions regarding a search algorithm based on the Grover Iteration.

Lets assume I would have a classical database:

Binary Index   Value
00             3
01             1
10             0
11             2

1. In the examples I have seen a register of lets say 2 qubits + 1 ancilla qubit (for the orcale) are used. Next, a uniform superposition of the 2 qubits is generated, followed by $r$-iterations of the oracle and diffusion operator. In the examples, people are using an oracle e.g. for the state "11" and ideally they finally measure "11" with $P = 1$. But this is not realy what we want in a database (?). How could I load the database shown above and search within it (e.g. to find the number "3") using the algorithm. In the end, I would be interested in the Index of an element I am searching for, right?

Imaginge I would have the following database:

Binary Index   Value
00             5
01             1
10             0
11             2

I would now like to search for "3" within this database. I would expect that the Grover algorithm would return $P = 0$ in this case.

2. There is another question regading the efficiency $\sqrt{N}$ of a $N$-dimensional database. Since we measure only the states "00", "01", ... "11" by a single shot, we would need to measure $i$-times to get a certain probability of our search element, e.g. "11". Would this not affect the actual efficiency of the algorithm? I understand when $N$ is a large number, the angle of rotation per iteration becomes small, so that after the rotations the database and search item are almost perfectly aligned. In this case we do not need to measure many times because the probability for "11" would be almost $P = 1$?

Answer 1

1. I'm not exactly sure what you're asking. Grover's algorithm works when you have an oracle operator $O_f$ such that $$O_f|x\rangle |0\rangle = |x\rangle |f(x)\rangle,$$ where $f(x)\in\{0,1\}$. For lots of applications (like your example) we have a function $g:\{0,1\}^n\rightarrow\{0,1\}^m$, i.e., the output is not a single bit, and we want to find the pre-image of some output. In your example, $g$ represents a look-up in the table, so $g(0)=3$, $g(1)=1$, etc. To translate this to the function for a Grover operator, we assume we have $$O_g:|x\rangle |0^m\rangle = |x\rangle |g(x)\rangle$$ (the second register has $m$ qubits). Then we create some equality operator for the specific point we're searching for. In your example, if we're looking for $3$, we would create an operator $O_{=3}$ such that $$O_{=3}|x\rangle |0\rangle = |x\rangle |0\rangle$$ if $x\neq 3$ and $$O_{=3}|x\rangle|0\rangle = |x\rangle | 1\rangle$$ if $x=3$. Then $O_{=3}O_g$ has the desired effect (if we apply $O_{=3}$ t the output register of $O_g$, and if we uncompute the output of $O_g$ after).

If the Grover search then returns an index $x$, and you want to find the value associated to $x$, then because we implement $O_g$ in this way, we can just run $O_g |x\rangle |0\rangle$ and measure the second register (of course, in your example, that will just give us 3, which we already know because that was the goal of our search!).

If you're actually searching a database, maybe there is more data associated to that index. For example, a database of students might have "student ID" and "major", and you want to find the major of the student with ID=3. So you find the index in the database of the student with ID=3, then look up that index to find the major.

1(b): Asking how you load the database: well, Grover's search isn't actually well suited for database search. How do you actually implement $O_g$? This relies on something called "QRAM" (sometimes called "QROM" or "QRACM"). This is a bit controversial and while there are some dubious proposals for a physical device that would efficiently do this, building it out of traditional quantum gates is quite expensive: essentially you iterate over the entire table, and write the corresponding value if the input matches.

But, if you iterate over the entire table, this costs $O(N)$. For that cost, you might as well search the database classically! So unless you believe in cheap QRAM (I don't) then Grover's algorithm is actually unhelpful for database search. It is a continuous annoyance to myself and others that Grover's algorithm is often described as a "database search" when it is really best described as a "pre-image search".

1(c): If you run a Grover search and the specific element is not in the "table" (i.e., there is no $x$ such that $f(x)=1$), then you end up with a uniform distribution over output values. Thus, when you measure, you'll get a uniformly random $x$. You would need to check the value of $x$ by computing $f$ (either classically or quantumly) to check whether the search succeeded or not.

2. You're basically right: the point of Grover's algorithm is amplify the probability of the correct answer (in your example, "11") so that when you measure at the end, the probability of measuring that answer is almost 1. So if you do the right number of Grover iterations, there is no extra complexity to repeat the measurements. (Though the probability won't be exactly 1, so you repeat maybe $O(1)$ times).