Promise of Graph Sparsification and Decomposition for Noise Reduction in QAOA: Analysis for Trapped-Ion Compilations

تخيل أنك تحاول حل عقدة ضخمة ومتشابكة من الخيوط. في عالم الحوسبة الكمومية، هذه "العقدة" هي مسألة رياضية معقدة تسمى Max-Cut، حيث يكون الهدف هو تقسيم مجموعة من الأشياء إلى فريقين بحيث تكون الروابط بين الفريقين أقوى ما يمكن. لفك هذه العقدة، يستخدم العلماء أداة خاصة تسمى QAOA (خوارزمية التحسين التقريبي الكمومي). فكر في QAOA كإنه روبوت يحاول إيجاء أفضل طريقة لقص الخيط عن طريق تحريكه ذهابًا وإيابًا. ولكن، هناك عقبة: الروبوت هش للغاية. أي دفعة بسيطة من البيئة المحيطة — مثل عطسة أو اهتزاز صغير — يمكن أن تجعل الروبوت يتعثر، ويفسد الحسابات، ويعطي إجابة خاطئة. هذا "الاصطدام" يسمى الضجيج الكمومي (quantum noise)، وهو السبب الأكبر وراء معاناة الحواسيب الكمومية اليوم في حل المسائل الكبيرة.

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

الفكرة الكبرى للورقة: جعل العقدة أخف

طور المؤلفون، وهم فريق من الباحثين من جامعات ومختبرات وطنية مرموقة، طريقة جديدة لتجهيز المسائل للحواسيب الكمومية. لقد ركزوا على نوع معين من الآلات الكمومية يسمى محاكي الأيونات المحتجزة (trapped-ion simulator). يمكنك تخيل هذه الآلات كذرات صغيرة عائمة مثبتة في مكانها بواسطة الليزر، تعمل كدماغ للروبوت. هذه الآلات بارعة في القيام بمهام معينة، ولكن عندما تحاول حل مسألة Max-Cut على رسم بياني (graph) يحتوي على العديد من الاتصالات (الحواف/edges)، فإنها تصبح مثقلة. الطريقة التقليدية لترجمة المسألة لهذه الآلات تتضمن الكثير من "النبضات" (مثل ومضات الليزر) و"قلب البتات" (مثل قلب مفتاح التشغيل). بالنسبة لرسم بياني يحتوي على $n$ من النقاط، كانت الطريقة القديمة تتطلب حوالي $n^2$ من النبضات. هذا قدر هائل من ومضات الضوء، وكل ومضة تعطي النظام فرصة ليصبح صاخباً ومشوشاً.

النتيجة الرئيسية للورقة هي أنه باستخدام التخفيف و التفكيك، يمكنهم تقليل عدد هذه النبضات والقلبات بشكل كبير دون فقدان جودة الإجابة. لقد أثبتوا رياضياً أنه إذا كنت مستعداً لقبول خسارة طفيفة ومسيطر عليها في مثالية الإجابة (لنفترض، أن تكون بنسبة 90% أو 95% مثالية بدلاً من 100%)، فيمكنك تقليل عدد النبضات من رقم ضخم قدره $n^2$ إلى شيء أصغر بكثير، مثل $n \log(n)$.

لتصور ذلك، تخيل شبكة ضخمة وكثيفة من 397 خيطاً تربط بين النقاط. الطريقة القديمة تقول إنه يجب عليك شد كل خيط من الخيوط بشكل فردي لحل المسألة. الطريقة الجديدة تقول: "انتظر! يمكننا إزالة معظم الخيوط والشد فقط على أهم 48 خيطاً، أو تقسيم الشبكة إلى شبكتين أصغر وأبسط". النتيجة؟ سيبذل الروبوت جهداً أقل بكثير. في عمليات المحاكاة التي أجروها، أظهروا أنه بالنسبة للعديد من الرسوم البيانية، يمكنهم قطع عدد العمليات بنسبة تصل إلى 80% مع الاستمرار في الحصول على حل لا يقل جودة عن أفضل حل ممكن.

كيف فعلوا ذلك: الخدعتان السحريتان

استخدم الباحثون تقنيتين رئيسيتين لتحقيق ذلك، وقد اختبروهما على مكتبة من الرسوم البيانية الصعبة تسمى MQLib.

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

• النتيجة: هذا يقلل عدد الحواف (الاتصالات) من عدد ضخم إلى عدد أقل بكثير، يتناسب تقريباً مع عدد النقاط ($n$) بدلاً من مربع عدد النقاط ($n^2$).
• العقبة: تشير الورقة إلى أنه بالنسبة لنوع محدد من الضجيج الذي صمموا به محاكاة الأيونات المحتجزة (يسمى dephasing)، فإن مجرد إزالة الحواف لم يساعد دائماً في تحسين الإجابة النهائية في تلك المحاكاة تحديداً. ومع ذلك، يجادلون بأنه في السيناريوهات الواقعية مع أنواع أخرى من الضجيج، فإن وجود حواف أقل لإدارتها يجب أن يظل مكسباً كبيراً لأن هناك أماكن أقل لحدوث الأخطاء.

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

• التشبيه: تخيل أنك تريد بناء برج من الطوب بأحجام وألوان مختلفة. الطريقة القديمة هي محاولة وضع كل طوبة فريدة واحدة تلو الأخرى. الطريقة الجديدة هي أن تقول: "حسناً، سأبني طبقة من الطوب الأحمر الصغير، ثم طبقة من الطوب الأزرق الكبير، ثم طبقة من الطوب الأخضر المتوسط". أنت تبني البرج في طبقات بسيطة ومنتظمة.
• النتيجة: سمح لهم هذا بتقليل عدد نبضات الليزر المطلوبة من $O(n^2)$ إلى $O(n \log(n/\epsilon))$. باللغة البسيطة، إذا كانت الطريقة القديمة تحتاج إلى 10,000 نبضة، فقد تحتاج الطريقة الجديدة إلى بضع مئات فقط. هذا تحسن هائل، خاصة مع كبر حجم المسألة.

ماذا وجدوا: المحاكاة والضمانات

لم يكتفِ الفريق بالتخمين؛ بل أجروا عمليات محاكاة حاسوبية مفصلة وأثبتوا رياضياتهم.

• الأرقام: بالنسبة لرسم بياني يحتوي على $n$ من العقد، احتاجت الطريقة القديمة إلى حوالي $n^2$ من النبضات. قللت طريقتهم الجديدة هذا الرقم إلى حوالي $n \log(n/\epsilon)$، حيث $\epsilon$ هي كمية الخطأ الضئيلة التي أنت مستعد لقبولها. بالنسبة لإجمالي عدد العمليات (النبضات بالإضافة إلى قلب البتات)، قللوها من $n^2$ إلى حوالي $n \log(n/\epsilon) / \epsilon^2$.
• الأداء: في عمليات المحاكاة باستخدام رسوم بيانية من مكتبة MQLib، وجدوا أنهم يستطيعون تقليل عدد العمليات بنسبة تصل إلى 80% مع الحفاظ على جودة الحل (نسبة التقريب) فوق 0.95 (أي 95% من أفضل إجابة ممكنة).
• اختبار الضجيج: عندما قاموا بمحاكاة ضجيج "dephasing" (الاهتزاز) الذي يحدث في تجارب الأيونات المحتجزة، كانت طريقة التفكيك هي الفائز الواضح. فقد حافظت على جودة الحل بمستوى أعلى بكثير من الطريقة القديمة. ومن المثير للاهتمام أن في نموذج الضجيج الخاص بهم، لم تظهر عملية التخفيف وحدها فائدة كبيرة لأن الوقت الذي استغرقته عملية المحاكاة لم يتغير كثيراً. ومع ذلك، يشير المؤلفون إلى أن هذا قد يكون مختلفاً في الحياة الواقعية حيث توجد أنواع أخرى من الضجيج، وأن امتلاك اتصالات أقل يجب أن يساعد بالتأكيد.

ما لم يذكروه (وما استبعدوه)

من المهم معرفة ما لا تدعيه هذه الورقة.

• ليست حلاً سحرياً شاملاً: هم لا يقولون إنهم حلوا مشكلة الضجيج تماماً. هم يقولون إن هذه التقنيات هي "أدوات مفيدة" تقلل من حجم المسألة، لكن الضجيج لا يزال عقبة رئيسية.
• ليس انتصاراً للحوسبة الكلاسيكية: هم يقرون بأن الحواسيب الكلاسيكية لا تزال أسرع بكثير في حل هذه المسائل من الحواسيب الكمومية في الوقت الحالي. هدفهم هو جعل الحواسيب الكمومية أفضل حتى تتمكن في النهاية من المنافسة، وليس القول بأنهم فازوا بالفعل.
• خاصة بالأيونات المحتجزة (غالباً): بينما تعمل الرياضيات مع أنواع أخرى من الحواسيب الكمومية أيضاً، فإن الإثبات المحدد لتقليل عدد النبضات مصمم لآلات الأيونات المحتجزة التي تستخدم تفاعلات "الكل مع الكل" (all-to-all). بالنسبة للآلات الأخرى (مثل الكيوبتات فائقة التوصيل)، فإن الفائدة تتعلق أكثر بتقليل إجمالي عدد البوابات، مما يحسن نظرياً "الدقة" (fidelity) (فرصة الحصول على الإجابة الصحيحة) بشكل أسي.
• المحاكاة مقابل الواقع: النتائج المتعلقة بنموذج الضجيج المحدد (dephasing) تم استخلاصها من معادلات رياضية وعمليات محاكاة. لم يجروا هذه التجارب على حاسوب كمومي فيزيائي في هذه الورقة؛ بل أظهروا أن النظرية تصمد في المحاكاة.

لماذا هذا مهم

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

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