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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو

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

بررسی کلی[ویرایش]

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

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

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

تقویت دامنه[ویرایش]

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

منابع[ویرایش]

Wikipedia contributors, "Quantum Algorithm" Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/Quantum_algorithm