2
$\begingroup$

If Grover algorithm has a better speed than classical search algorithms, would it be an example of where Quantum computers outruns classical computers?

Can we use Grover Algorithm in real world problems?

$\endgroup$
2
$\begingroup$

A Grover algorithm outperform classical unordered database search algorithms quadratically. So, it can serve as an example of higher performance of quantum computers. However, when complexity of Grover search is assessed, generally a complexity of an oracle is ignored. In some cases the oracle complexity is so high that it cancels out advantage of faster search.

Currently, Grover search cannot be used for real world problems because of high noise level and decoherence quantum computers suffer from. However, once these problems are solved, Grover search can be employed naturally for unordered database search and optimization tasks.

$\endgroup$
2
  • $\begingroup$ Thanks Martin! I was curious because Shor's algorithm is more famous than Grover Algorithm. Maybe I am wrong! $\endgroup$
    – radar101
    Dec 21 '20 at 10:48
  • 1
    $\begingroup$ @radar101: You are welcome. I would not say that Shor algorithm is more famous but it was the first one showing how useful quantum computer can be. Shor and Grover algorithms were introduced almost together (Shor in 1994 and Grover in 1996). Also Shor algorithm reaches exponential speed up, while Grover one only quadratic speed up. Therefore, these algorithms are used as an example that quantum computer bring different increase in velocity of problems solving. May I ask you to accept my answer, if it is satisfactory for you? $\endgroup$ Dec 22 '20 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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