1
$\begingroup$

I'd like to start with saying sorry if my question makes no sense as I'm a physics student, but only in third year.

I've discovered Grover's algorithm, but what I'm not sure of is if it could be used as a real database or if it's for searching something like an array? For example if you had a database column of strings 8-chars long could you use Grover's algorithm to search for a match (let's say x='quantumc')?

Then my follow up question is would you need 64 logical qubits to make this calculation? (8 binary bits x 8 characters)

Thanks in advance!

Improve this question
$\endgroup$
3

2 Answers 2

Reset to default
3
$\begingroup$

Many many people refer to Grover's algorithm as a "database search" but this is not a very good description of what it does. It's actually an algorithm that searches for a solution that makes an oracle function return True, where an oracle function is a function that, given an input, outputs whether or not the input is the solution to a problem you want to solve. Grover&s algorithm is much closer to a boolean-sat solver in that sense. It is not a practical way to build a database. I hope your confusion has been solved!

Improve this answer
$\endgroup$
1
  • $\begingroup$ ah thanks! who would have thought this stuff would be confusing, eh $\endgroup$
    – Max Rush
    Commented Jan 23, 2022 at 17:19
0
$\begingroup$

In addition to that link, if you know some programming/python, you might want to check the Qiskit textbook entry for Grover's algorithm. Also not that a database is an organized collection of structured information. So when we say "search in database" we're not necessarily saying search in some oracle/mysql database, but if needed, the algorithm can be implemented to search in a database with some key-value association.

could you use Grover's algorithm to search for a match (let's say x='quantumc')?

Yes you can. It's done at the oracle step, the oracle will simply answer "yes it's the element we want" or "no it's not".

Then my follow up question is would you need 64 logical qubits to make this calculation? (8 binary bits x 8 characters) The reasoning is not accurate... to answer your question I will give an example. Given an array that has 42 elements, how many bits do I need in order to express the index when I find the value I am looking for? to express the indices up to 42 you need 6 bits. So you need 6 qubits.

You can convince yourself with an example. watch this video, or simply copy the implementation from the qiskit textbook

https://www.youtube.com/watch?v=0RPFWZj7Jm0&ab_channel=Qiskit

Try to run the code on a real quantum machine from IBM with a limited number of qubits or even using the simulator

Or you can use this notebook (from Qiskit summer school lab2): https://www.dropbox.com/s/plo3lcq0vb0jipo/QSS2020-lab2.ipynb?dl=0

Further reading: https://web.eecs.umich.edu/~imarkov/pubs/jour/cise05-grov.pdf

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks! I really appreciate it. This might be something I can add to my resume too haha :) $\endgroup$
    – Max Rush
    Commented Oct 24, 2021 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.