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

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

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

کاربردهای الگوریتم گِرُوِر

مشکلاتی در پیاده سازی الگوریتم گرور وجود دارد:

１- مشکل اول اینکه اگر قرار است در این الگوریتم از یک اوراکل استفاده کنیم، اول باید آن را بسازیم و اگر مواظب نباشیم تعداد قدمهای لازم برای ساختن اوراکل بیشتر از تعداد قدمهایی می شود که الگوریتم برای ما صرفه جویی می کند و در نهایت باعث می شود که الگوریتم از معادل کلاسیک آن کندتر شود نه سریعتر.

２- مشکل دوم این که این تسریع محاسبات با این فرض انجام می شود که هیچ ترتیبی در دیتا وجود ندارد. اگر ساختاری در دیتا وجود داشته باشد می توان الگوریتم های کلاسیکی را یافت که از این ساختار استفاده می کنند و پاسخ را با روشی بهتر از حدس زدن پیدا می کنند.

این دو مورد نشان می دهد که الگوریتم گرور در شرایط خاصی می تواند از الگوریتم های کلاسیک بهتر عمل کند. جالب است بدانید که ثابت شده که الگوریتم گرور بهینه است یعنی هیچ الگوریتم کوانتومی نمی تواند بیش از الگوریتم گرور جستجو در یک پایگاه داده نامرتب را بهبود دهد.^[۱]

از نکته های بالا می توان نتیجه گرفت که مهمترین کاربردهای الگوریتم گرور نه برای خود الگوریتم بلکه برای نسخه های تغییریافته آن خواهد بود. به هرصورت الگوریتم شور و الگوریتم گرور تا زمان نگارش این مطلب مهمترین الگوریتم های کوانتومی به شمار می روند و الگوریتم های زیادی بر پایه این دو طراحی شده اند.^[۲]^[۳]

جستارهای وابسته

منابع

مشارکت‌کنندگان ویکی‌پدیا. «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.
↑ Bernhardt, C. (2019). Quantum Computing for Everyone. The MIT Press. MIT Press. p. 180-181. ISBN 978-0-262-03925-3. Retrieved 2023-01-16.
↑ Shor, Peter W. (2003). "Why haven't more quantum algorithms been found?". Journal of the ACM. Association for Computing Machinery (ACM). 50 (1): 87–90. doi:10.1145/602382.602408. ISSN 0004-5411.

پیوند به بیرون

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_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.

[Bernhardt_2019_p._7-2] Bernhardt, C. (2019). Quantum Computing for Everyone. The MIT Press. MIT Press. p. 180-181. ISBN 978-0-262-03925-3. Retrieved 2023-01-16.

[Shor_2003_pp._87–90-3] Shor, Peter W. (2003). "Why haven't more quantum algorithms been found?". Journal of the ACM. Association for Computing Machinery (ACM). 50 (1): 87–90. doi:10.1145/602382.602408. ISSN 0004-5411.

[۱]

[۲]

[۳]