Understand Grover's Algorithm: Classical Problem vs Quantum Solution

[paweld]

Could anyone explain me how Grover's algorithm works.
I read the article on wiki about it:
http://en.wikipedia.org/wiki/Grover_algorithm"
but I don't see any relation between classical problem of searching an
element in unsorted database and its alledge quicker quantum solution.

In classical problem we have a set of unsorted objects from and we want
to find one particular object. What is the quantum counterpart of this?

 

[xts]

I think it is a kind of misunderstanding to call it a 'database search' (Grover is responsible for that misleading title)
What the algorithm really does is to find that unique value for which the (quantum-computational) function returns 1, while for all other possible states it returns 0. You may call this function a 'comparison with a key for database', but that seems to be very simplified analogy.

You may want to read original Grover's paper: http://arxiv.org/abs/quant-ph/9605043

However I haven't heard about any Grover's realisation other than trivial (algorithm returns the input value, the function to be used is a Kronecker's delta)

 

[paweld]

I think it is a kind of misunderstanding to call it a 'database search' (Grover is responsible for that misleading title)

I agree with you. I think that one can compare this algorithm to algorithm of
finding an argument for which a given function has particular value.

I only don't understand why so many people claim that quantum computing
surpasses classical one, because the Grover's algorithm
searches unsorted database in $$O(\sqrt{n})$$
whereas the best classical algorithm is linear. For me these two algorithms
solve slightly different problems.

 

[xts]

I think that one can compare this algorithm to algorithm of finding an argument for which a given function has particular value.

Yes, it is what actually Grover's algorithm does.
Just with some restrictions: there must be exactly one argument such, that function returns that value. And - what much worse - the function must be possible to be implemented as a quantum algorithm.

 

[Joseph14]

Yes, it is what actually Grover's algorithm does.
Just with some restrictions: there must be exactly one argument such, that function returns that value. And - what much worse - the function must be possible to be implemented as a quantum algorithm.

I'm curious about which functions that can be implemented classically are theoretically hard to implement with a quantum algorithm?

 

[PatrickPowers]

I'm curious about which functions that can be implemented classically are theoretically hard to implement with a quantum algorithm?

Classical computation is a subset of quantum computation. So anything you can do classically can be done with a quantum computer. I think you know that, and are meaning to ask, with which problems is it difficult to take advantage of the quantum nature of the machine?

The advantage of quantum computers is massive parallelism. You will find that with most problems parallelism does surprisingly little or no good. According to the theorists quantum computers won't help solve problems in NP.

 

[PatrickPowers]

I'm curious about which functions that can be implemented classically are theoretically hard to implement with a quantum algorithm?

Hmm, how about data base search? If the data base is in ordinary computer storage it seems to me that a quantum algorithm would not help you at all. The data would have to be stored as quantum superpositions.

But I could be wrong about this.

 

[Joseph14]

Hmm, how about data base search? If the data base is in ordinary computer storage it seems to me that a quantum algorithm would not help you at all. The data would have to be stored as quantum superpositions.

But I could be wrong about this.

thanks