Grover's Algorithm: is it really a search algorithm

In summary: It seems to me that the algorithm has to be supplied with the desired state in the first place, so what is the point of the algorithm? How does it even relate to searching?In summary, Grover's algorithm is a quantum algorithm that uses a combination of quantum mechanics and mathematical operators to find a specific element in an unsorted database. It involves an Oracle operator that negates the sign of the element being searched for and a Grover operator that rotates the input state to converge on the target state. While it may not be directly analogous to classical database searching, it has practical applications in tasks such as Monte Carlo Integration. Additionally, a more general version of the algorithm has been developed that does not rely on specific starting and target states
  • #1
gulsen
217
0
I'm wondering how it really is useful.

The input for the, say 2-qubit, quantum computer that is running Grover's algoritm is
[tex]|\Psi \rangle = (|1 \rangle + |2 \rangle + |3 \rangle + |4 \rangle) / \sqrt{4}[/tex]
And let us say we're looking the 3rd element in the so-called database.

Now, Grover operator involves the Oracle operator, which basically negates the sign of the element we're looking for, i.e. sign of [tex]|3 \rangle[/tex], which means [tex]O=I-2 |3 \rangle \langle 3 |[/tex]. The operator can be written in the obvious basis as

[tex]O = \[ \left( \begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & -1 & 0 \\
0 & 0 & 0 & 1 \\
\end{array} \right)\] [/tex]

And the Grover operator is [tex]G = (2 |\Psi \rangle \langle \Psi | - I) O[/tex]

Anyway, upon acting "enough" on the input state, our output is roughy [tex]|3 \rangle[/tex], i.e.

[tex]|3 \rangle \approx G^n |\Psi \rangle[/tex]

How is this output useful? Other than this, if this is the big result, how come do we use the state [tex]|3 \rangle[/tex] in reaching this result (it was a part of Oracle operator, right?)

I've suddenly started to think it was some sort of a hoax but then it's not, and now I think I'm missing some crucial point, something I fail to see. Please show me how this is a "(unordered) database search"...
 
Physics news on Phys.org
  • #2
I have the same problem you do. I don't think it's analogous to a database search. The analog of a database in QC would be a quantum state. But in Grover's algorithm, you are not given a state, but rather an operator O. In an actual implementation of QC, this would be a device for manipulating qbits. The analogy would be hard-wiring your "database" into your computer.

Caveat: I am not a QC expert. Perhaps one will weigh in and explain why this is wrong.
 
  • #3
Can it be used to search an unalphabetized phone book for a phone number, faster than classical? I don't see how, as it requires that you know the answer a priori to construct the quantum circuit.

However, it is a useful technique. Note that it consists of a product of sqrt(N) identical queries. Each query has polynomial complexity and consists of a rotation by an angle of order 1/sqrt(N). The full product of queries is a rotation by about pi/2 and has exponential complexity.

The idea is useful for tasks other than unstructured search. For example, it allows one to do Monte Carlo Integration in sqrt(N) steps instead of N steps, using the idea of quantum counting (Ref.http://qbnets.wordpress.com/2009/02/21/classical-reversible-computing-and-quantum-computer-programming/" [Broken])
 
Last edited by a moderator:
  • #4
I've written a blog post that tries to answer this question.
http://qbnets.wordpress.com/2010/01/06/grovers-algorithm-for-dummies/" [Broken]
 
Last edited by a moderator:
  • #5
I too am having a problem understanding the use of this algorithm (sorry for necro-posting).

My problem is that I'm trying to construct an emulation of Grover's search within Matlab. However, by following the mathematical operations discussed in Grover's paper and from other sources I can collapse the uniform distribution of N=2^n states down to the desired state, but I fail to see how to put this into practice.

Say I have an unordered list of binary digits, each entry 4 digits in length. How would I find the index of entry '1101'? Following the operations in the literature I have at hand I simply end up with the qubit formulation of |1101> giving me seemingly no new info.

I realize I must be completely missing something here, but what it is I cannot fathom. I wish the literature was a lot clearer on the matter.

If anyone could help with my understanding here, I'd be eternally grateful.
 
  • #6
I was trying to construct an emulation of the grover algorithm in MATLAB myself which you can find here:
http://folk.uio.no/anderhaf/grover.m [Broken]

The whole point is that you have a problem where you have a total of 2^n possible states, and 0 < k < (2^n)/2 states are solutions to a specific problem. The oracle can easily check whether a state is a solution or not. In problems like this, one can usually only iterate through the whole space and check if every state is a solution or not. With quantum mechanics and grovers algorithm, you can do it quicker then possible in the classical way.
 
Last edited by a moderator:
  • #7
I'll give you an analogy that might help you. Suppose you know a series that converges to a constant pi whose value you don't know a priori. Think of the Grover oracle as a subroutine that gives you only partial information about the series each time you call the subroutine. Your goal is to find the limit of the series. Grover's algorithm helps you to calculate that limit by calling the oracle fewer times than you would have to, classically.

By the way, http://qbnets.wordpress.com/2010/01/28/my-secret-life-as-a-captain-of-the-grovers-algorithm/" [Broken] that I wrote of a more general version of Grover's algorithm(GA). This new version is more general in two important ways:

(1)It does not require that <s|t> be of small, where |s> is the starting state and |t> is the target state. (The original GA only works if <s|t> ~1/sqrt(N) )
(2)It converges with absolute certainty to the target state (The original GA converges only with a finite probability.)
 
Last edited by a moderator:
  • #8
Wow thanks. But regarding your final comment rrtucci; how does it collapse down to the target state with absolute certainty? I thought your could only get closer and closer to a probability of 1 as you increase the number of qubits used in the system?
 
  • #9
The "fixed-point" algorithm converges exactly to the target instead of "flying" close to it but not hitting it. It's all explained in the paper
 
  • #10
Intriguing, thank you.

Edit: Great blog by the way (The Raven is coincidentally my favourite poem).
 
  • #11
Hello, me again. I'm still incrediably confused regarding this algorithm. I just cannot see how this algorithm gives the actual location in an unsorted list of a desired state. I can increase the amplitude of the desired state starting from the uniform distribution easily enough and collapse it down to the desired state with the appropriate probabilities, but this tells me nothing about the actual location of this state.

What is it that I'm missing? Am I really being that daft that I can't grasp that which many claim to be a simple concept?

I follow the algorithm as defined in the literature to the letter and get the desired state as an output... but I already know what this desired state looks like since it is my desired state. So what new info has grover's algorithm granted me?

I am hopelessly lost and any help would be greeted with the utmost gratitude.
 
  • #12
Sorry I didn't answer sooner but I didn't see your latest post until today.
I think what is confusing you is that people often use for the Grover oracle a subroutine (i.e. quantum circuit) from which it is obvious by looking at it what the target state is. For Grover's algorithm to be REALLY useful, you want to use an oracle from which it is NOT obvious what the target state is. Suppose the target was e, the base of the natural logs. An example of the useless, first case would be a subroutine that had inside it a declaration of a constant equal to 2.719. An example of the second case would be a subroutine that calculated a Taylor series that you had never seen before but which turned out to converge to e.
 
Last edited:

1. What is Grover's Algorithm and how does it work?

Grover's Algorithm is a quantum algorithm designed to efficiently search through an unsorted database. It works by using quantum parallelism and interference to amplify the amplitude of the correct answer while canceling out the amplitudes of incorrect answers, making the correct answer stand out.

2. Is Grover's Algorithm a true quantum search algorithm?

Yes, Grover's Algorithm is considered a true quantum search algorithm because it uses quantum principles and can perform the search faster than any classical algorithm.

3. What are the advantages of using Grover's Algorithm compared to classical search algorithms?

Grover's Algorithm has the advantage of being able to search through an unsorted database in significantly fewer steps than classical algorithms, making it a much more efficient option for certain types of problems.

4. Are there any limitations or drawbacks to using Grover's Algorithm?

One limitation of Grover's Algorithm is that it can only search through unsorted databases, so if the data is already sorted, it may not be the most efficient approach. Additionally, the algorithm relies on quantum computers, which are currently not widely available.

5. Can Grover's Algorithm be used for any type of search problem?

No, Grover's Algorithm is specifically designed for searching through unsorted databases. It is not suitable for other types of problems, such as optimization or constraint satisfaction.

Similar threads

  • Quantum Physics
Replies
1
Views
744
Replies
3
Views
770
  • Quantum Physics
Replies
11
Views
1K
  • Quantum Physics
Replies
4
Views
577
Replies
4
Views
2K
  • Quantum Physics
Replies
9
Views
896
Replies
1
Views
564
  • Quantum Physics
Replies
2
Views
887
Replies
12
Views
1K
Back
Top