Unitary complexity in polynomial space

في عالم الحوسبة، يوجد انقسام جوهري بين ما يمكن للآلة القيام به بسرعة، وما يمكنها القيام به إذا أُعطيت قدرًا هائلًا من الذاكرة. لعقود من الزمن، رسم علماء الحاسوب خرائط لهذه المناطق، ووضعوا فئات للمشكلات السهلة الحل، والمشكلات الصعبة الحل، والمشكلات التي يبدو من المستحيل حلها ضمن أي إطار زمني معقول. ويتمثل سؤال مركزي في هذا المجال فيما إذا كانت القدرة على استخدام المزيد من الذاكرة تسمح للحاسوب بحل مشكلات تقع تمامًا خارج نطاق وصول حاسوب ذي ذاكرة محدودة. وبينما لدينا شكوك قوية حول الإجابات، إلا أن العديد من هذه الأسئلة لا تزال دون إثبات.

بالتوازي مع هذا العالم الكلاسيكي، يبرز مجال الحوسبة الكمومية، حيث تستخدم الآلات الخصائص الغريبة للجسيمات دون الذرية لمعالجة المعلومات. هنا، القواعد مختلفة؛ فالحاسوب الكمومي لا يكتفي بمجرد قلب البتات (bits) من حالة التشغيل إلى الإيقاف أو العكس، بل يتلاعب بأمواج معقدة من الاحتمالات. وهذا يسمح له بأداء مهام معينة قد تستغرق من الحاسوب الكلاسيكي دهرًا. ومع ذلك، ظل لغز عميق قائمًا: هل تعتمد قوة الحوسبة الكمومية على نوع جديد تمامًا من الصعوبة، أم أنها في السر مجرد نسخة فعالة للغاية من الحوسبة الكلاسيكية متنكرة؟ وتحديدًا، تساءل الباحثون عما إذا كان من الممكن تفكيك كل عملية يمكن للحاسوب الكمومي القيام بها إلى سلسلة من الخطوات التي يمكن لحاسوب كلاسيكي استيعابها في نهاية المطاف، إذا حصل على التلميحات المناسبة. فإذا كانت الإجابة بنعم، فإن القوة الفريدة للتشفير الكمومي قد تكون وهمًا. أما إذا كانت الإجابة بلا، فإن الحواسيب الكمومية تمتلك قوة جوهرية لا يمكن للآلات الكلاسيكية محاكاتها أبدًا.

لقد اتخذ باحثان، ويليام كريتشمر وإوين تانج، مؤخرًا خطوة كبيرة نحو حل حالة عدم اليقين هذه. لم يحل الباحثان اللغز بالكامل، لكنهما بنيا جسرًا منطقيًا قويًا يربط وجود التشفير الكمومي الآمن ببعض أقدم وأكثر المشكلات استعصاءً في علوم الحاسوب الكلاسيكية. ويشير عملهما إلى أنه إذا وجد تشفير كمومي آمن في العالم الحقيقي، فإن أحد أمرين يجب أن يكون صحيحًا: إما أن هناك حدًا جوهريًا لمدى جودة ترجمة العمليات الكمومية إلى تعليمات كلاسيكية، أو أن سؤالًا محددًا، يعود لعقود مضت، حول قوة الحواسيب الكسلاسيكية يجب أن يحصل على إجابة مفاجئة.

لفهم إنجازهما، يجب على المرء أولاً أن يستوعب طبيعة المهمة التي يحللانها. تخيل الحاسوب الكمومي كجهاز يمكنه تدوير جسم متعدد الأبعاد بطريقة قابلة للعكس تمامًا. تسأل "مشكلة التركيب الوحدوي" (unitary synthesis problem) عما إذا كان بإمكاننا، لأي تدوير من هذا القبيل، إيجاد مجموعة من التعليمات الكلاسيكية التي يمكن لحاسوب قياسي اتباعها لإعادة إنشاء ذلك التدوير. فلو استطعنا دائمًا القيام بذلك، لكان ذلك يعني أن العالم الكمومي هو، بشكل من الأشكال، مجرد نسخة معقدة جدًا من العالم الكلاسيكي. وقد ركز الباحثان على فئة محددة من هذه الدورات: تلك التي يمكن للحاسوب الكمومي القيام بها باستخدام قدر معقول من الذاكرة. وتساءلا عما إذا كان يمكن دائمًا تركيب هذه الدورات المحددة بواسطة حاسوب كلاسيكي بمساعدة "أوراكل" (oracle)، وهو في الأساس صندوق أسود سحري يمكنه الإجابة فورًا على أسئلة محددة.

بدأ المؤلفان بمعالجة عقبة عملية: كيفية تعريف هذه المهام الكمومية بدقة. لقد أدت المحاولات السابقة لتصنيفها إلى نتائج مربكة، جزئيًا لأنها سمحت بترك "نفايات" (garbage) خلفها أثناء الحساب. في الحوسبة الكمومية، عندما تقوم الآلة بعملية حسابية، فإنها غالبًا ما تترك وراءها بيانات إضافية لم تعد ضرورية ولكن لا يمكن حذفها ببساطة دون التأثير على النتيجة. بعض التعريفات سمحت بهذه البيانات المتبقية الفوضوية، بينما طالبت تعريفات أخرى بعملية نظيفة تمامًا. وقد أظهر كريتشمر وتانج أنه بالنسبة للمهام التي تتضمن كميات كبيرة من الذاكرة، فإن هذا التمييز لا يهم. فقد أثبتا أن أي عملية كمومية فوضوية مليئة بالنفايات يمكن تحويلها إلى عملية نظيفة خالية من النفايات دون تغيير الصعوبة الجوهرية للمهمة. وكانت هذه خطوة حاسمة، حيث سمحت لهما بالتعامل مع هذه العمليات الكمومية المعقدة بمستوى من الوضوح الرياضي الذي كان مفقودًا.

ومع وضع هذه التعريفات، شرعا في معالجة السؤال الجوهري. فقد أثبتا أنه لأي عملية كمومية يمكن تنفيذها باستخدام مساحة حدودية (polynomial space) -أي كمية معقولة من الذاكرة- فهناك احتمالان فقط: إما أن العملية معقدة للغاية بحيث لا يمكن لأي حاسوب كلاسيكي، مهما بلغ ذكاؤه أو مقدار المساعدة التي يتلقاها من "الأوراكل"، أن يركبها بكفاءة؛ أو أن العملية ليست بتلك الصعوبة؛ إذ يمكن تركيبها بكفاءة إذا سُمح للحاسوب الكلاسيكي بطرح أسئلة حول نوع معين من المشكلات الصعبة المعروفة باسم "مشكلة بحث NEXP". وتعد هذه الفئة الثانية معيارًا مرتفعًا جدًا في نظرية التعقيد الكلاسيكية، حيث تمثل مشكلات هي أصعب أسيًا من أصعب المشكلات التي نعرف حاليًا كيفية حلها.

إن تداعيات هذا الاكتشاف عميقة، لا سيما بالنسبة لمستقبل التشفير. يعتمد التشفير الكمومي على فكرة أن بعض المهام، مثل إنشاء "مخطط التزام" (commitment scheme) آمن -وهي طريقة لقفل سر في صندوق رقمي بحيث لا يمكن تغييره أو التلصص عليه- هي مهام يستحيل على الخصم كسرها. وإذا وجدت التزامات كمومية آمنة، فإن منطق الباحثين يملي علينا أننا في موقف محدد للغاية: إما أن مشكلة التركيب الوحدوي لها إجابة سلبية، مما يعني وجود عمليات كمومية تتجاوز في جوهرها قدرة التركيب الكلاسيكي، أو أن سؤالًا كلاسيكيًا رئيسيًا حول التعقيد يجب أن يُحل. وتحديدًا، سيعني ذلك أن فئة من المشكلات تسمى BPP (المشكلات التي يمكن حلها بسرعة باستخدام الاحتمالات العشوائية) لا تساوي NEXP (المشكلات التي يمكن حلها بالزمن الأسي وعدم التحديد). وهذا سؤال ظل مفتوحًا لأكثر من أربعين عامًا.

بكلمات أبسط، تجادل الورقة بأن إثبات وجود تشفير كمومي آمن ليس مجرد مسألة بناء أجهزة كمومية أفضل، بل هو مرتبط ارتباطًا وثيقًا بالحدود النظرية العميقة للحوسبة الكلاسيكية. فإذا استطعنا إثبات أمن الالتزامات الكمومية بشكل غير مشروط، فسنضطر في الوقت نفسه إلى الإجابة على أحد لغزين ضخمين من ألغاز العقود الماضية في علوم الحاسوب. فإما أن نضطر لقبول أن العمليات الكمومية يمكن أن تكون أصعب جوهريًا في المحاكاة مما اعتقدنا، أو أننا سنضطر إلى إثبات أن نوعًا معينًا وقويًا للغاية من الحوسبة الكلاسيكية هو بالتأكيد أكثر قدرة من الحوسبة العشوائية القياسية.

كما يسلط هذا البحث الضوء على العلاقة بين القوة الكمومية والكلاسيكية بمعناها العام. فقد أظهر المؤلفان أنه إذا افترضنا أن مشكلة التركيب الوحدوي لها إجابة إيجابية (أي أن كل شيء يمكن تركيبه)، فإن قوة الحواسيب الكمومية ذات الذاكرة الكبيرة مقيدة بدقة بقوة الحواسيب الكلاسيكية التي تحل مشكلات بحث NEXP. وهذا يشير إلى أن "سحر" الحوسبة الكمومية، إن وجد، ليس ظاهرة عائمة بحرية، بل هو متجذر بعمق في بنية التعقيد الكلاسيكي. فإذا استطاعت الحواسيب الكمومية القيام بشيء جديد حقًا، فذلك لأنها تصل إلى طبقة من الصعوبة لا يمكن للحواسيب الكلاسيكية الوصول إليها، حتى مع أفضل الطرق المختصرة.

في نهاية المطاف، لا يخبرنا هذا البحث ما إذا كان التشفير الكمومي آمنًا أو ما إذا كانت مشكلة التركيب الوحدوي قابلة للحل. بدلاً من ذلك، فإنه يرسم تضاريس المنطقة بين هذين الاحتمالين. إنه يكشف أن الطريق إلى إثبات أمن الأنظمة الكمومية مسدود بنفس الجدران التي منعت علماء التعقيد الكلاسيكي من حل أصعب مشكلاتهم لنصف قرن. وتقترح الورقة أننا لا يمكننا ببساة "بناء" طريقنا نحو الإثبات؛ بل يجب علينا أولًا فهم الحدود الجوهرية للحوسبة نفسها. ومن خلال توضيح التعريفات وإقامة هذه الروابط الصارمة، قدم كريتشمر وتانج رؤية أوضح للمشهد، موضحين أن مصير التشفير الكمومي ومصير نظرية التعقيد الكلاسيكي مرتبطان معًا بطريقة لم تكن مفهومة من قبل.