ما المسائل التي تتميز فيها الحواسيب الكمومية؟
شاهد فيديو تطبيقات الحوسبة الكمومية من تقديم أوليفيا لينز، أو افتح الفيديو في نافذة منفصلة على YouTube.
مقدمة
في الدرس السابق، تناولنا مسألة واحدة بعمق — حل مشكلة القطع الأقصى (Max-Cut) باستخدام صياغة QUBO. اليوم سنتبع نهجاً مختلفاً ونناقش التطبيقات قصيرة المدى بشكل أوسع. سنبدأ بإعطائك فكرة عن كيفية تحديدنا لأنواع المسائل التي قد تستفيد من حل كمومي. ثم سنستعرض بعض الأمثلة الحديثة من أعمال مجتمعنا. سيساعدك هذا على بناء حدسك تجاه أنواع المسائل المناسبة للحوسبة الكمومية وكيفية التعامل معها.
الصعوبة الكلاسيكية مقابل الكمومية
قبل الخوض في الأمثلة، دعنا نناقش أولاً كيف ندرس صعوبة المسائل المختلفة ونصنفها. بعض المسائل يُحل بسهولة على الحاسوب الكلاسيكي ولا نحتاج حاسوباً كمومياً لحلها. في المقابل، هناك مسائل بالغة الصعوبة تستلزم الحواسيب الكمومية لحلها. من أشهر الأمثلة إيجاد العوامل الأولية للأعداد الصحيحة الكبيرة. يعتمد تشفير RSA على صعوبة هذه المشكلة، وصُمِّمت خوارزمية شور لحلها على حاسوب كمومي. مثال آخر هو إيجاد حل في مجموعة بيانات غير مرتبة — يمكن حل ذلك نظرياً بخوارزمية جروفر الكمومية. غير أن معظم الخبراء يتفقون على أن هذه الأنواع من الخوارزميات تستلزم تطبيق تصحيح الأخطاء، والتكنولوجيا لم تصل إلى ذلك المستوى بعد.
لذا نبحث عن مسائل يمكننا معالجتها في منطقة التوازن بين السهل جداً والصعب جداً — مسائل يستطيع حلّها حواسيب اليوم الكمومية لكنها تُعيق الحواسيب الكلاسيكية.
فئات التعقيد
تُصنَّف صعوبة هذه المسائل وتُحلَّل في فرع من علوم الحوسبة يُسمى نظرية تعقيد الحوسبة. يوجد عدد كبير من فئات التعقيد في الحوسبة الكلاسيكية، لكن أبرزها:
- P: المسائل التي يمكن حلها في وقت متعدد الحدود مع تزايد حجم المسألة. هي مسائل سهلة الحل.
- NP: تعني "غير حتمية متعددة الحدود". هذه المسائل لا يمكن بالضرورة حلها في وقت متعدد الحدود، لكن يمكن التحقق من صحة إجاباتها في وقت متعدد الحدود.
- NP-كاملة: أصعب المسائل في NP وليس لها حل متعدد الحدود معروف. هنا تعيش مسائل شهيرة كمسألة البائع المتجول ولعبة السودوكو.
- BPP، أو المسائل متعددة الحدود محدودة الخطأ، وهي مسائل يمكن حلها ضمن عتبة خطأ معينة بحاسوب كلاسيكي احتمالي في وقت متعدد الحدود.
عندما اختُرع مفهوم الحوسبة الكمومية، بذل الناس جهوداً كبيرة لمعرفة أي فئة من المسائل ستستطيع هذه الأنواع الجديدة من الحواسيب حلها بكفاءة. فاختُرعت فئة جديدة من المسائل:
- BQP، أو المسائل الكمومية متعددة الحدود محدودة الخطأ. هذا المكافئ الكمومي لـBPP: هي فئة مسائل القرار التي يمكن لحاسوب كمومي حلها في وقت متعدد الحدود باحتمال خطأ صغير.