How is the Grover-Algorithm applied to a database?

Question

Question

I want to use the Grover-Algorithm to search an unsorted database for an element $x$. Now the question arises, how do I initialize index and value of the database with the qubits?

Example

• Let's say I have $4$ qubits. Thus, $2 ^ 4 = 16$ classical values can be mapped.
• My unsorted database $d$ has the following elements: $d [\text{Value}] = [3,2,0,1]$.
• I want to search for $x = 2_d = 10_b = |10\rangle$.
• My approach: index the database $d$ with $d [(\text{Index, Value})] = [(0,3), (1,2), (2,0), (3,1)]$. Registers $0$ and $1$ for the index and registers $2$ and $3$ for the value. Then apply the Grover-Algorithm only to registers $2$ and $3 (\text{Value})$. Can this be realized? Is there another approach?

What I already implemented (on GitHub)

The "Grover-Algorithm with 2-, 3-, 4-Qubits", but what it does is simple: the bits are initialized with $|0\rangle$, the oracle will mark my solution $x$ (which is just a number like $2_d = 10_b$), the Grover part will increase the probability of the selected element $x$ and decrease all other probabilities and then the qubits are read out by being mapped to the classical bits. We let this process run several times in succession and thus obtain a probability distribution, where the highest probability has our sought element $x$.

The output is always the same as the one marked in the oracle. How can I generate more information from the output, that I do not know at the time when I constructed the oracle?

Answer 1

I've been working on this problem as well. As a beginner and a classical programmer (i.e., I don't speak Quantum Mechanics), it is difficult to get an understanding of the concepts without complete examples. I've been working with the Microsoft Q# Database Search sample. It simply searches for a specific index/key in the database, which is not very useful. I have expanded upon that sample to search a list of values in a database and return the corresponding key.

As with your example, there is one two-qubit "key register" for the indexes, and a separate two-qubit register for the values. There is also a fifth "marked qubit" that comes from Microsoft's sample, to indicate when the desired value is found. The keys and values are associated via entanglement. That is best demonstrated with a circuit. Click here to see the actual Quirk circuit.

Note that this circuit contains only the oracle. It does not implement all of Grover's algorithm.

• The top two qubits are the key register, the next two are the value register, and the bottom qubit is the marked qubit.
• The first section puts the key register in a uniform superposition using Haramard gates, as required by Grover's algorithm.
• The second section is where the keys are associated with the values via entanglement. Each key is entangled with a corresponding value in the value register by applying (Anti-)Controlled X gates. So, when the key register is 0, then the value register will be set to 3. When the key is 1, the value is set to 2, and so on on.
• The third section of the circuit is the search oracle. The value register is entangled with the marked qubit. In this example, the desired value is 2. When the value register contains 2, the marked qubit will be set to 1.
• Grover's algorithm looks at the key register and marked qubit. The search oracle looks at the value register and sets the marked qubit. This will cause key 1 to be amplified when the value is 2.

It's interesting to note that the keys and values are not stored in the qubits, but rather in the circuit/program. You could say it's not really a database per se. It's more like a switch/case statement, but one that can run on a superposition of values.

For more details, caveats, and Q# code, see my GitHub repository.

EDIT: Something I understand better since answering... you have to reverse/undo the circuit as part of each iteration. In the Q# code, the Adjoint StatePreparationOracle() call within the ReflectStart() operation handles this, so I didn't have to do it explicitly. I don't know if Qiskit has a similar feature. If I've done the translation properly, here is a complete circuit for the example above.

Answer 2

You need to convert the oracle to hold the database too, as a result, the general Oracle (Phase Inversion) will have two sub-oracles take a look the figure.

The first sub-oracle that have to prepared is the memory circuit, in contrast to QRAM which stores quantum data (state) in its body, this memory (array) circuit is prepared to store only classical information in its frame. An example of such kind of circuit that stores an array of binaries [010, 110, 100, 011] is displayed below: For more read this paper.

Answer 3

When presenting Grover's algorithm as applied to search in a database, it is supposed that the Oracle has access to the elements of the classical list. Yet it is a very strong assumption and this is why we represent that by a controlled-selector using CNOT/Toffolis of an index representing simply this operation (like the Toffoli circuit in the case $n=4$).

You mention the approach of computing the values in another register : $$ \sum_i | i\rangle | d(i)\rangle $$ You assume again you are given an oracle for doing so and efficiently (a straightforward way is to control-NOT but you have to do this for every index/value so not very efficient). In this case, the oracle would be the function $ f(i)= 2 $ in a quantum circuit format (again a controlled-selector), marking this state and continue with Grover iterations.

I think it is better to think of the quantum search algorithm as optimizing a function, instead of searching in a list/database. Here is an article I worked on where quantum search is used for solving a combinatorial maximization problem if you want to pursue further your understanding of the algorithm.

Answer 4

I have a sample with qiskit sample link