الگوریتم گرور
الگوریتم گِرُوِر (به انگلیسی: Grover's algorithm) یک الگوریتم کوانتومی برای جستجو در یک پایگاه داده نامرتب دارای N عضو، در زمانِ (O(N و در فضای ذخیرهسازی (O(log N است. لُو گرور این الگوریتم را در سال ۱۹۹۶ مطرح کرد.
بر روی یک رایانه کلاسیک، جستجو در یک پایگاه داده نامرتب نمیتواند در زمان کمتر از زمان خطی یا (O(n، یعنی با بررسی تک تک ورودیها انجام گیرد. الگوریتم گرُوِر بیان میکند که روی یک رایانه کوانتومی این عمل با پیچیدگی زمانی (O(N قابل انجام است و بهطور حدی، سریعترین الگوریتم قابل پیادهسازی برای جستجوی پایگاه دادهٔ نامرتب روی یک رایانه کوانتومی است. با وجود اینکه که الگوریتمهای کوانتومی معمولاً افزایش سرعتی نمایی نسبت به الگوریتمهای کلاسیک دارند ٬این الگوریتم افزایش سرعتی از توان ۰٫۵ در پی دارد که البته برای Nهای بزرگ بسیار قابل توجه است.
جستارهای وابسته
پیوند به بیرون
- Grover's Algorithm simulation and circuit diagram.
- Grover’s Quantum Search Algorithm animated explanation.
- [۱] simulation and circuit diagram with cats.
مطالعه بیشتر
- Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
- Grover L.K.: From Schrödinger's equation to quantum search algorithm, American Journal of Physics, 69(7): 769-777, 2001. Pedagogical review of the algorithm and its history.
- Nielsen, M.A. and Chuang, I.L. Quantum computation and quantum information. Cambridge University Press, 2000. Chapter 6.
- What's a Quantum Phone Book?, Lov Grover, Lucent Technologies
- Grover's Algorithm: Quantum Database Search, C. Lavor, L.R.U. Manssur, R. Portugal
- Grover's algorithm on arxiv.org
منابع
- ↑ Bennett C.H.، Bernstein E.، Brassard G.، Vazirani U.، The strengths and weaknesses of quantum computation. SIAM Journal on Computing 26(5): 1510–1523 (1997). Shows the optimality of Grover's algorithm.