Grover's Algorithm: is it really a search algorithm

[gulsen]

I'm wondering how it really is useful.

The input for the, say 2-qubit, quantum computer that is running Grover's algorithm is
|\Psi \rangle = (|1 \rangle + |2 \rangle + |3 \rangle + |4 \rangle) / \sqrt{4}
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 |3 \rangle, which means O=I-2 |3 \rangle \langle 3 |. The operator can be written in the obvious basis as

O = \[ \left( \begin{array}{cccc}<br /> 1 &amp; 0 &amp; 0 &amp; 0 \\<br /> 0 &amp; 1 &amp; 0 &amp; 0 \\<br /> 0 &amp; 0 &amp; -1 &amp; 0 \\<br /> 0 &amp; 0 &amp; 0 &amp; 1 \\<br /> \end{array} \right)\]

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

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

|3 \rangle \approx G^n |\Psi \rangle

How is this output useful? Other than this, if this is the big result, how come do we use the state |3 \rangle 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"...

 

[Avodyne]

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.

 

[rrtucci]

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/" )

 

[rrtucci]

I've written a blog post that tries to answer this question.
http://qbnets.wordpress.com/2010/01/06/grovers-algorithm-for-dummies/"

 

[Nishido]

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.

 

[Andeplane]

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

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.

 

[rrtucci]

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/" 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.)

 

[Nishido]

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?

 

[rrtucci]

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

 

[Nishido]

Intriguing, thank you.

Edit: Great blog by the way (The Raven is coincidentally my favourite poem).

 

[Nishido]

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.

 

[rrtucci]

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.