3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "real-world" example might be too big for any quantum algorithm, for maybe another decade, or maybe longer! $\endgroup$ – user1271772 Nov 1 '18 at 9:47
  • $\begingroup$ @user1271772 i didn't expect the example data to be really big, just a few hundreds or thoundsands lines, see how it work. There're ppl claim that qiskit already can do this with csv file so i wonder if Q# can do it too $\endgroup$ – Huang Lee Nov 1 '18 at 9:53
  • 2
    $\begingroup$ I don't think Grover can be used to search "real databases", at least in the way I'd define database. I never understood why people sell Grover as searching databases. $\endgroup$ – Norbert Schuch Nov 1 '18 at 12:26
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ if it search through inputs of a function, can i replace the original function with a C# function like compare a string with a list on it. Will it run faster than normal c# code? If you have experience with Q# $\endgroup$ – Huang Lee Nov 1 '18 at 10:17
  • $\begingroup$ So the function here is the oracle, which is directly coded as quantum gates and the inputs are the binary strings formed by superposition. You submit a real quantum circuit actually. $\endgroup$ – cnada Nov 1 '18 at 10:23
  • $\begingroup$ @HuangLee I edited my answer with the example to help you visualize. $\endgroup$ – cnada Nov 1 '18 at 10:41
  • $\begingroup$ one more questions, it say time to run the function to find the value only take 2^n/2 (n is the amount of possible data). Will this apply to the quantum simulation as well or real quantum computer only? $\endgroup$ – Huang Lee Nov 1 '18 at 10:48
  • 1
    $\begingroup$ @cnada ok, that's about it, you've been a great help, thanks :D $\endgroup$ – Huang Lee Nov 1 '18 at 11:22

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.