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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
answered Dec 16, 2020 at 14:38
-
$\begingroup$ Thanks Martin! I was curious because Shor's algorithm is more famous than Grover Algorithm. Maybe I am wrong! $\endgroup$– radar101Commented Dec 21, 2020 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$ Commented Dec 22, 2020 at 7:31
-
$\begingroup$ "high noise level" how bad is it? $\endgroup$ Commented Feb 8, 2022 at 12:28
-
1$\begingroup$ @SamGinrich: I was not able to run instances with more than 3 qubits on IBM Q (free-tier processors), i.e. we are currently restricred to toy-model database with only four records. $\endgroup$ Commented Feb 9, 2022 at 9:37
-
$\begingroup$ This [Reference][1] from 2019 names 8-30% error for typical dimension of a 14 QuBit-engine, meets the accuracy of mental arithmetic and reads like "RSA as scalable algorithm will be save for long time". [1]: memlab.ece.gatech.edu/papers/MICRO_2019_1.pdf $\endgroup$ Commented Feb 9, 2022 at 9:52