Practical example of Grover's algorithm (in Q#)

Question

Is there any real example for Grover's algorithm but with real database (generated from SQL or file)? I download the Q# development kit & its example, there was one call DatabaseSearchExample claim to use Grover's but it technically doesn't have any kind of database. May I ask a code for this if available?

Answer 1

So far, it is better to say that the Grover Search algorithm, while presented as an algorithm searching through a database, would not be suited for such purpose. We prefer to say that we search through inputs of a function (the famous oracle). Loading the database/list in a quantum form would be costly in terms of qubits so for now it is not the best application. When presenting, we say that the oracle will have access to the elements of the list/database, but it is not applicable at that time.

I remember seeing an example of using Grover for SAT problems in Qiskit. There was a notebook showing an example on 3 qubits, and the oracle was built so that it would select the binary combination satisfying a set of clauses. They changed much the files now so you may not see it in the github for Qiskit. You were seeking through all possible combinations using superposition and I think it was a good practical example not involving list/database.

To help you visualize the example, say you have such 3 clauses to satisfy : $$ f(x_1, x_2, x_3) = (x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_1 \vee \neg x_2 \vee \neg x_3) \wedge (\neg x_1 \vee x_2 \vee x_3) $$

with $x_1,x_2,x_3$ binary values. We seek a combination ($x_1,x_2,x_3$) such that f equals 1. We can have all the possible combinations of ($x_1,x_2,x_3$) using the Hadamard transform (000,001,010,...) so we don't need to input a list here. If you provide the f function as a quantum operator, that is a set of gates for applying f onto the combinations presented in basis states, with one application you can compute the result of the function in parallel.

And in Grover's algorithm, using a qubit oracle in the $ |-\rangle $ state, you compute the output of f into it, which makes a phase kickback $ (-1)^{f(x_1,x_2,x_3)}|-\rangle $, marking with a minus sign the combinations for which f equals 1.

Using the Grover diffusion operator, you amplify the amplitudes of the good combinations, to increase their probability of being measured as output of the circuit by measurement.