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

الگوریتم کوانتومی الگوریتمی است که بر مدلی واقع گرا از یک کامپیوتر کوانتومی (به انگلیسی: quantum computer) اجرا می‌شود. پر استفاده‌ترین مدل، مدلی است که از مدار کوانتومی (به انگلیسی: quantum circuit) استفاده می‌کند. الگوریتم کلاسیک روشی است که هر مرحلهٔ ان بر روی کامپیوترهای کلاسیک قابل اجرا باشد و در مقابل ان الگوریتم کوانتومی روشی است که هر مرحلهٔ ان بر روی کامپیوترهای کوانتومی قابل اجرا باشد. مسئله‌های غیرقابل حل با الگوریتم‌های کلاسیک همچنان با الگوریتم کوانتومی غیرقابل حل است. اما مزیت الگوریتم کوانتومی این است که مسئله‌های قابل حل با زمان کمتری حل می‌شوند. معروف‌ترین الگوریتم‌های کوانتومی الگوریتم شور برای تجزیه به عوامل اول و الگوریتم گرور برای جستجو در یک پایگاه داده نامرتب است. الگوریتم شور به صورت نمایی از بهترین الگوریتم کلاسیکی که تجزیه به عامل اول را انجام می‌دهد بهتر عمل می‌کند و همین‌طور الگوریتم گرور به اندازهٔ رادیکال زمان بهترین الگوریتم کلاسیک با عملکرد مشابه زمان می‌گیرد.

بررسی کلی

الگوریتم‌های کوانتومی معمولاً با مدل مداراتی از محاسبات کوانتومی مدل می‌شوند که این مدار کوانتومی بر روی کیوبیت‌های ورودی تأثیر می‌گذارد و ان‌ها را با اندازه‌گیری نابود می‌کند. هر مدار کوانتومی شامل یک گیت کوانتومی (به انگلیسی: quantum gate) است که بر تعداد ثابتی از کیوبیت‌ها تأثیر می‌گذارد (معمولاً ۲ یا ۳). الگوریتم‌های کوانتومی می‌توانند با مدل‌های کوانتومی دیگر مانند مدل همیلتون اراکل(به انگلیسی: Hamilton oracle model) مدل شوند. الگوریتم‌های کوانتومی را بر اساس تکنیک‌هایی که استفاده می‌کنند به دو دستهٔ کلی الگوریتم‌هایی که از تبدیل فوریهٔ کواتومی استفاده می‌کنند و الگوریتم‌هایی که از تقویت دامنه استفاده می‌کنند تقسیم می‌کنند.

تبدیل فوریه کوانتومی

تبدیل فوریه کوانتومی معادل کوانتومی تبدیل فوریه گسسته است. تبدیل فوریه کوانتومی بر روی کامپیوتر کوانتومی که از اردر یک چند جمله‌ای گیت کوانتومی دارد اجرا شود.

تقویت دامنه

تقویت دامنه تکنیکی است که در ان یک فضای فرعی از حالت‌های کوانتومی تقویت می‌شوند. معمولاً الگوریتم‌هایی که از تقویت دامنه استفاده می‌کنند زمانشان به صورت رادیکالی نسبت به الگوریتم کلاسیکشان کاهش می‌یابد. می‌توان گفت الگوریتم‌هایی که از این تکنیک استفاده می‌کنند تعمیم الگوریتم گرور هستند.

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

• الگوریتم کوانتومی
• اطلاعات کوانتومی
• الگوریتم شور
• الگوریتم گرور