باز کردن منو اصلی

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

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

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

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

مطالعه بیشترویرایش

منابعویرایش

  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.