الگوریتم گرور

الگوریتم گِرُوِر (به انگلیسی: Grover's algorithm) یک الگوریتم کوانتومی برای جستجو در یک پایگاه داده نامرتب دارای N عضو، در زمانِ (O(N^۱/۲ و در فضای ذخیره‌سازی (O(log N است. لُو گرور این الگوریتم را در سال ۱۹۹۶ مطرح کرد.

بر روی یک رایانه کلاسیک، جستجو در یک پایگاه داده نامرتب نمی‌تواند در زمان کمتر از زمان خطی یا (O(n، یعنی با بررسی تک تک ورودی‌ها انجام گیرد. الگوریتم گرُوِر بیان می‌کند که روی یک رایانه کوانتومی این عمل با پیچیدگی زمانی (O(N^۱/۲ قابل انجام است و به‌طور حدی، سریع‌ترین الگوریتم قابل پیاده‌سازی برای جستجوی پایگاه دادهٔ نامرتب روی یک رایانه کوانتومی است.[1] با وجود اینکه که الگوریتم‌های کوانتومی معمولاً افزایش سرعتی نمایی نسبت به الگوریتم‌های کلاسیک دارند ٬این الگوریتم افزایش سرعتی از توان ۰٫۵ در پی دارد که البته برای 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

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Grover's algorithm». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۳ خرداد ۱۳۹۲.

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[bennett_1997-1] 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.