الگوریتم گرور
الگوریتم گِرُوِر (به انگلیسی: 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