1. یادگیری بیشتر:
افزایش سرعت کوانتومی به مزیتی اشاره دارد که کامپیوترهای کوانتومی میتوانند در حل برخی مسائل محاسباتی نسبت به کامپیوترهای کلاسیک به دست آورند. به طور خاص، افزایش سرعت کوانتومی زمانی رخ میدهد که یک الگوریتم کوانتومی بتواند مسئلهای را کارآمدتر (از نظر زمان یا منابع) نسبت به بهترین الگوریتم کلاسیک شناختهشده حل کند. این مفهوم در قلب قدرت محاسبات کوانتومی قرار دارد و ناشی از اصول منحصربهفرد مکانیک کوانتومی، مانند برهمنهی و درهمتنیدگی است که به کامپیوترهای کوانتومی اجازه میدهد اطلاعات را به روشهایی پردازش کنند که کامپیوترهای کلاسیک از آن ناتوان هستند.
افزایش سرعت کوانتومی به دو دسته اصلی تقسیم میشود:
1. افزایش سرعت کوانتومی نمایی
افزایش سرعت نمایی کوانتومی به مواقعی اشاره دارد که یک الگوریتم کوانتومی میتواند مسئلهای را به طور نمایی سریعتر از هر الگوریتم کلاسیک شناختهشده، حل کند؛ به این معنا که الگوریتم کوانتومی پیچیدگی زمانی مسئله را از یک تابع نمایی به یک تابع چندجملهای کاهش میدهد.
مثال: الگوریتم شور
الگوریتم شور، که توسط پیتر شور در سال 1994 توسعه یافت، یک الگوریتم کوانتومی برای تجزیه اعداد صحیح است. تجزیه یکی از مسائل اساسی در نظریه اعداد میباشد و بر یافتن یافتن اعداد اولی که با هم ضرب میشوند تا یک عدد صحیح مشخص را تولید کنند، دلالت دارد.
کارآمدترین الگوریتم شناختهشده کلاسیکی برای تجزیه اعداد صحیح زمان زیرنمایی نیاز دارند، به این معنا که حل این مسئله برای اعداد بزرگ به قدری طول میکشد که عملاً غیرممکن است و از این مرتبه میباشد:
چرا افزایش سرعت نمایی؟
در محاسبات کلاسیک، تجزیه اعداد بزرگ با افزایش اندازه عدد، به طور نمایی دشوارتر میشود. الگوریتم شور از ویژگیهای کوانتومی مانند پردازش موازی کوانتومی و تبدیل فوریه کوانتومی استفاده میکند تا این مسئله را سریعتر حل کند. توانایی پردازش همزمان بسیاری از روشهای ممکن برای تجزیه (به لطف برهمنهی کوانتومی) کلید موفقیت این الگوریتم است.
این شتاب نمایی قابل اثبات است، زیرا با تحلیل ریاضی پیچیدگی زمانی الگوریتم در مقایسه با روشهای کلاسیک، پشتیبانی میشود.
افزایش سرعت کوانتومی چندجملهای
افزایش سرعت چندجملهای به پیشرفت نسبتاً محدودتر اما همچنان مهم در سرعت محاسبات اشاره دارد. در این افزایش سرعت، الگوریتم کوانتومی پیچیدگی زمانی مسئله را با یک عامل چندجملهای نسبت به بهترین روشهای کلاسیک شناختهشده کاهش میدهد.
مثال:الگوریتم گروور
الگوریتم گروور، که توسط لاو گروور در سال 1996 توسعه یافت، افزایش سرعت درجه دوم برای جستجو در پایگاههای داده بدون ساختار فراهم میکند. این مسئله معمولاً به عنوان جستجوی یک لیست بدون ساختار برای یافتن یک آیتم خاص توصیف میشود.
در محاسبات کلاسیک، جستجو در یک لیست بدون ساختار با N عنصر در بدترین حالت به O(N) مرحله نیاز دارد؛ به عبارتی اگر لیستی با N عنصر داشته باشیم، یک الگوریتم جستجوی کلاسیک ممکن است مجبور باشد تکتک عناصر را بررسی کند تا به هدف برسد که این کار زمان متناسب با N میطلبد.
الگوریتم گروور میتواند این پایگاه داده را در زمانی برابر با O(√N) جستجو کند. این افزایش سرعت درجه دوم است، چرا که تعداد مراحل مورد نیاز را از یک تابع خطی O(N) به یک تابع جذر، O(√N)، کاهش میدهد. اگرچه این شتاب نمایی نیست، اما همچنان یک پیشرفت قابل توجه، به ویژه برای مجموعهدادههای بسیار بزرگ است.
چرا افزایش سرعت درجه دو؟
ایده اصلی پشت الگوریتم گروور استفاده از برهمنهی کوانتومی و تقویت دامنه است. جستجوی گروور با ایجاد برهمنهی از تمام پاسخهای ممکن آغاز میشود و سپس به طور سیستماتیک دامنه احتمال پاسخ درست را افزایش میدهد. با هر تکرار، احتمال یافتن پاسخ درست افزایش مییابد تا اینکه پس از حدود √N مرحله، احتمال یافتن راهحل به شدت بالا میرود.
2. اصول کلیدی:
· برهمنهی و پردازش موازی: افزایش سرعت کوانتومی به طور بنیادی از خاصیت برهمنهی ناشی میشود که این برهمنهی به کامپیوترهای کوانتومی اجازه میدهد چندین احتمال را به طور همزمان پردازش کنند (پردازش موازی).
· تداخل کوانتومی: الگوریتمهای کوانتومی به تداخل سازنده و مخرب متکی هستند تا پاسخهای درست را تقویت کرده و پاسخهای نادرست را حذف کنند. این اصل به طور گسترده در الگوریتمهایی نظیر الگوریتمهای شور و گروور مورد استفاده قرار میگیرد.
· کلاسهای پیچیدگی: محاسبات کلاسیک و کوانتومی اغلب از منظر کلاسهای پیچیدگی مورد بررسی قرار میگیرند. مسائلی که در زمان چندجملهای توسط کامپیوترهای کلاسیک قابل حل هستند، در کلاس P قرار میگیرند. در حالی که مسائلی که توسط کامپیوترهای کوانتومی در زمان چندجملهای حل میشوند (مانند آنچه الگوریتم گروور انجام میدهد)، در کلاس BQP (Bounded-error Quantum Polynomial time) قرار دارند. الگوریتم شور، که مسائلی مانند تجزیه اعداد به عوامل اول را در زمان چندجملهای حل میکند، نشان میدهد که برخی مسائل که در محاسبات کلاسیک دشوار هستند (و احتمالاً خارج از کلاس P قرار دارند)، ممکن است برای کامپیوترهای کوانتومی در کلاس BQP باشند.
محدودیتهای عملی
در حالی که افزایش سرعت کوانتومی به طور ریاضیاتی برای برخی الگوریتمها ثابت شده است، مواردی را باید در نظر گرفت:
· تمامی مسائل از افزایش سرعت کوانتومی بهره نمیبرند: الگوریتمهای کوانتومی برای انواع خاصی از مسائل مانند تجزیه اعداد، جستجو و شبیهسازیهای کوانتومی بیشترین کارآمدی را دارند.
- دوران (NISQ ) محاسبات کوانتومی نویزی و مقیاس متوسط : کامپیوترهای کوانتومی فعلی، نویزی و از نظر اندازه دارای محدودیت هستند؛ به این معنا که افزایش سرعت کوانتومی به طور کاربردی هنوز به طور کلی گسترده نشان داده نشده است. با این حال با بهبود سختافزارهای کوانتومی، انتظار میرود کاربردهای بیشتری ظاهر شوند.
3. تاریخچه:
ریچارد فاینمن در سال ۱۹۸۱ پیشنهاد داد که سیستمهای کوانتومی نمیتوانند بهطور مؤثر توسط کامپیوترهای کلاسیک، شبیهسازی شوند و این فرضیه را مطرح کرد که ممکن است کامپیوترهای کوانتومی در شبیهسازی مکانیک کوانتومی از کامپیوترهای کلاسیک پیشی بگیرند.
پیتر شور در ۱۹۹۴ الگوریتمی برای فاکتورگیری اعداد بزرگ ارائه داد که بهطور نمایی سریعتر از الگوریتمهای کلاسیک عمل میکرد. این دستاورد، تسریع نمایی کوانتومی را به نمایش گذاشت و علاقه به رمزنگاری و پیچیدگی محاسباتی را برانگیخت.
همچنین لوو گروور در ۱۹۹۶ الگوریتمی طراحی کرد که تسریع درجه دوم (Quadratic) را برای جستوجوی پایگاههای داده بدون ساختار فراهم میکرد. این الگوریتم نشان داد که کامپیوترهای کوانتومی میتوانند در طیف گستردهای از مسائل سرعت بیشتری ارائه دهند.
در دهه 1990 و پس از آن، پژوهشگران قدرت محاسبات کوانتومی را در قالب کلاس پیچیدگی BQP (زمان چندجملهای کوانتومی با خطای محدود) دستهبندی کردند. این کلاس شامل مسائلی است که کامپیوترهای کوانتومی میتوانند بهطور کارآمد حل کنند.
گوگل در سال ۲۰۱۹ ادعای دستیابی به برتری کوانتومی را مطرح کرد و مسئلهای خاص را بسیار سریعتر از ابرکامپیوترهای کلاسیک حل کرد، که توان بالقوه تسریع کوانتومی در کوتاهمدت را به اثبات رساند.