Understand Grover's Algorithm: Classical Problem vs Quantum Solution

  • Thread starter paweld
  • Start date
  • Tags
    Algorithm
In summary, Grover's algorithm finds a unique value for which the (quantum-computational) function returns 1, while for all other possible states it returns 0.
  • #1
255
0
Could anyone explain me how Grover's algorithm works.
I read the article on wiki about it:
http://en.wikipedia.org/wiki/Grover_algorithm" [Broken]
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?
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
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)
 
  • #3
xts said:
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 [tex]O(\sqrt{n})[/tex]
whereas the best classical algorithm is linear. For me these two algorithms
solve slightly different problems.
 
  • #4
paweld said:
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.
 
  • #5
xts said:
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?
 
  • #6
Joseph14 said:
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.
 
  • #7
Joseph14 said:
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.
 
  • #8
PatrickPowers said:
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
 

What is Grover's Algorithm?

Grover's Algorithm is a quantum algorithm that can efficiently search an unsorted database for a desired item. It uses quantum computing principles such as superposition and interference to significantly speed up the search process compared to classical algorithms.

What is the classical problem that Grover's Algorithm solves?

Grover's Algorithm solves the problem of searching an unsorted database. In classical computing, this problem would require checking each item in the database one by one, which becomes increasingly time-consuming as the database grows larger. With Grover's Algorithm, the search time is only proportional to the square root of the database size, making it much more efficient.

How does Grover's Algorithm work?

Grover's Algorithm works by using a series of quantum operations, such as applying a quantum oracle and performing quantum measurements, to manipulate the state of a quantum computer's qubits. This allows the algorithm to search the entire database in parallel and find the desired item with a high probability.

What makes Grover's Algorithm a quantum solution?

Grover's Algorithm utilizes quantum properties such as superposition and interference to efficiently search a database. These properties allow the algorithm to perform operations on multiple states simultaneously, resulting in a much faster search time compared to classical algorithms which can only operate on one state at a time.

What are the potential applications of Grover's Algorithm?

Grover's Algorithm has potential applications in areas such as data encryption, optimization problems, and database searching. It can also be combined with other quantum algorithms to solve more complex problems. With the development of quantum computers, Grover's Algorithm has the potential to significantly impact industries such as finance, healthcare, and logistics.

Suggested for: Understand Grover's Algorithm: Classical Problem vs Quantum Solution

Replies
6
Views
611
Replies
1
Views
684
Replies
2
Views
828
Replies
1
Views
635
Replies
1
Views
678
Replies
13
Views
791
Back
Top