On Multi-Constrained Path Finding utilizing Grover Search and Decoded Quantum Interferometry
تقترح هذه الورقة وتقيم خوارزميات كمومية، وتحديداً بحث غروفر مع تحضير حالة جديد كفء في استخدام الكيوبت والتداخل الكمومي المرموز (DQI)، لحل مشكلة إيجاد المسار متعدد القيود على الرسوم البيانية الموجهة غير الحلقية، مما يبرهن على تعقيدات بواباتها النظرية وأدائها التجريبي على معالجات IBM الكمومية مقابل خطوط أساس كلاسيكية قوية.
في الطرق السريعة الشاسعة وغير المرئية للإنترنت، تسافر حزم البيانات عبر مسارات يجب أن تستوفي مجموعة صارمة من القواعد. قد تحتاج مكالمة فيديو إلى مسار يتميز بتأخير منخفض، وتكلفة منخفضة، وحد من عدد التوقفات. إن إيجاد مسار واحد يلبي جميع هذه المتطلبات في آن واحد هو مشكلة لطالما أثارت إحباط مهندسي الشبكات. وعندما يكون هناك قاعدتان أو أكثر، ينمو عدد المسارات الممكنة بسرعة كبيرة لدرجة أن فحصها واحداً تلو الآخر يصبح مستحيلاً حتى بالنسبة لأقوى الحواسيب الفائقة. هذه أحجية كلاسيكية في علوم الحاسوب: كيف تتنقل في شبكة معقدة من الخيارات دون أن تضيع في الحجم الهائل للاحتمالات. لعقود من الزمن، اعتمدت أفضل الحلول على اختصارات ذكية أو تقريبات، ولكن يبقى السؤال عما إذا كان نوع جديد من الآلات، يستخدم القوانين الغريبة للفيزياء الكمومية، يمكنه حل هذه الأحجية بشكل أسرع من أي شيء نملكه اليوم.
تلقي هذه الورقة نظرة فاحصة على ذلك السؤال، حيث تختبر نهجين كموميين محددين مقابل أفضل الأساليب الكلاسيكية المتاحة. ركز الباحثون على نوع من الشبكات يسمى "الرسم البياني الموجه غير الدوري"، وهو في الأساس خريطة حيث يمكنك التحرك للأمام فقط ولا يمكنك العودة أبداً إلى الوراء. وقد تساءلوا عما إذا كانت الحواسيب الكمومية قادرة على إيجاد مسار يظل ضمن نطاقات محددة لعدة قياسات مختلفة، مثل الوقت والتكلفة. النهج الأول الذي اختبروه هو تقنية كمومية معروفة تسمى "بحث غروفر". تخيل محاولة العثور على مفتاح معين في غرفة مظلمة ضخمة مليئة بالمفاتيح المتطابقة. سيضطر الحاسوب الكلاسيكي إلى التقاطها واحداً تلو الآخر، لكن الحاسوب الكمومي يمكنه، بطريقة ما، النظر في العديد من المفاتيح في وقت واحد. بنى الباحثون دائرة كمومية تنشئ حالة "تراكب" لكل مسار ممكن عبر الشبكة، مما يضمن أن الآلة لا تنظر إلا في المسارات الصالحة فقط. ثم استخدموا "أوراكل" (Oracle) كمومياً لتحديد المسارات التي استوفت جميع القواعد وتضخيم الإشارة لتلك المسارات الجيدة.
ومع ذلك، كانت نتائج هذا النهج الأول واقعية ومثبطة. فبينما تعد الطريقة الكمومية أسرع نظرياً من البحث بالقوة الغاشمة، وجد الباحثون أنها لم تكن في الواقع أسرع من التقنيات الكلاسيكية الأفضل في أنواع الشبكات التي اختبروها. فالطريقة الكلاسيكية التي قارنوها بها، والمعروفة باسم "الالتقاء في المنتصف" (meet-in-the-middle)، تقوم بتقسيم الرحلة إلى نصفين والالتقاء في المركز، وتبين أنها فعالة بنفس القدر في أسوأ السيناريوهات. علاوة على ذلك، تطلبت الدائرة الكمومية عدداً هائلاً من العمليات — مئات الآلاف من البوابات المنطقية المعقدة — لحل حالة واحدة كان بإمكان الحاسوب الكلاسيكي حلها بأقل من عشرين ألف خطوة. ويخلص المؤلف إلى أنه بالنسبة لهذا النوع المحدد من مشاكل التوجيه، فإن التفوق الكمومي ليس موجوداً بعد؛ فالأدوات الكلاسيكية جيدة جداً ببساطة، والأجهزة الكمومية باهظة الثمن وعرضة للأخطاء لدرجة تمنعها من المنافسة.
استكشف النهج الثاني مساراً مختلفاً وأكثر تخصصاً. تعمل هذه الطريقة، التي تسمى "التداخل الكمومي لفك التشفير"، فقط على الشبكات ذات البنية المنتظمة والمحددة للغاية حيث تتبع القواعد نمطاً رياضياً صارماً. في هذا السيناريو، تتحول المشكلة إلى مهمة فك تشفير، تشبه إصلاح رسالة تالفة أُرسلت عبر خط مشوش. هنا، لا يبحث الحاسوب الكمومي عن الإجابة عن طريق فحص المسارات واحداً تلو الآخر، بل يستخدم "تحويل فورييه الكمومي" لإنشاء نمط تداخل يسلط الضوء بشكل طبيعي على أفضل الحلول. قام الباحثون بمحاكاة هذه الطريقة على عدة حالات ووجدوا أنها تستطيع تحديد المسارات التي تستوفي معظم القواعد بشكل أفضل من التخمين العشوائي أو الاستكمال الكلاسيكي البسيط. حتى أنهم أجروا نسختين صغيرتين من هذه المشكلة على أجهزة كمومية حقيقية من شركة IBM. وأظهرت النتائج أن الإشارة الكمومية صمدت أمام ضجيج الآلة، حيث حافظ الجهاز على حوالي 67 بالمائة من التحسن المثالي في الاختبار الأصغر و15 بالمائ@ في اختبار أكبر قليلاً.
رغم هذه العلامات الواعدة، تتوخى الورقة الحذر في رفع سقف التوقعات. فهذه الطريقة المتخصصة تعمل فقط على الشبكات التي تبدو كسلسلة من المراحل المتطابقة، وهي بنية نادراً ما توجد في توجيه الإنترنت في العالم الحقيقي. كما يشير الباحثون إلى أن الصعوبة الكلاسيكية للمشكلة في هذه الحالات الخاصة ليست مثبتة بالكامل، مما يعني أن التفوق الكمومي مدعوم بالأدلة وليس بضمان رياضي. كانت التجارب على الأجهزة الحقيقية صغيرة ولم تُجرَ إلا مرة واحدة، وتأثرت النتائج بشدة بالقيود الحالية للآلات الكمومية. يصرح المؤلف صراحة بأن عملهم لا يمثل طفرة في توجيه الشبكات العامة. بدلاً من ذلك، هم يقدمون خارطة طريق واضحة وصادقة لمكان وقوف الحواسيب الكمومية اليوم: يمكنها أداء مهام محددة وعالية الهيكلية مع لمحة من التفوق، ولكن بالنسبة للمشاكل المعقدة والواقعية المتعلقة بإيجاد المسارات الفعالة، تظل الحواسيب الكلاسيكية هي الأداة المتفوقة. وتعمل الدراسة كعملية مراجعة واقعية صارمة، تفصل بين الوعد النظري للسرعة الكمومية والقيود العملية للوقت الراهن.
ملخص تقني: إيجاد المسارات متعددة القيود عبر بحث غروفر والتداخل الكمي المفكك
بيان المشكلة تتناول الورقة مشكلة المسار متعدد القيود (MCP) على الرسوم البيانية الموجهة غير الحلقية (DAGs). الهدف هو إيجاد مسار من مصدر s إلى وجهة t بحيث يقع مجموع أوزان K من المقاييس الجمعية ضمن نطاقات محددة [Li,Ui] لجميع المقاييس. تم إثبات أن هذه المشكلة هي "ضعيفة الـ NP-complete" (weakly NP-complete) عندما تكون K≥2. وبينما توفر البرمجة الديناميكية الكلاسيكية حلولاً شبه متعددة الحدود، تبحث الورقة فيما إذا كانت الخوارزميات الكمية يمكن أن تقدم مزايا على الخطوط المرجعية الكلاسيكية القوية، لا سيما في الأطر التي تعاني فيها الطرق الكلاسيكية.
المنهجية يقترح المؤلف ويحلل نهجين كميين متميزين:
بحث غروفر على الرسوم البيانية العامة (DAGs):
تحضير الحالة: يقدم المؤلف دائرة تحضير حالة خالية من الكيوبتات المساعدة (US) تقوم بإنشاء تراكب منتظم لجميع مسارات s-t. يعتمد هذا البناء على استخدام كيوبت واحد لكل قوس ويعتمد على بنية الرسم البياني (DAG). يستخدم الترتيب الطوبولوجي حيث يتم تهيئة كيوبتات "الرمز" (token) ثم تقسيمها باستخدام دورات محكومة (Ry) وبوابات CNOT لتوزيع السعة بشكل متناسب مع عدد المسارات في الأسفل.
بناء الأوراكل (Oracle): يقوم أوراكل مقيد بالنطاق بتمييز المسارات التي تقع فيها جميع مجاميع المقاييس ضمن حدودها المعنية. يتضمن ذلك إضافة الأوزان للقوس بشكل محكوم إلى سجلات المجموع، والمقارنة مع الحدود، ثم إلغاء الحساب (uncomputation) لإعادة الكيوبتات المساعدة إلى الصفر.
البحث: تطبق الخوارمة تضخيم السعة لغروفر، مما يتطلب O(N/M) من استدعاءات الأوراكل، حيث N هو إجمالي عدد المسارات و M هو عدد المسارات الصالحة.
التداخل الكمي المفكك (DQI) على الأنسجة الخطية المتدرجة:
حالة خاصة: يستهدف هذا النهج فئة محددة من "الأنسجة المتدرجة" (staged fabrics) حيث يتكون الرسم البياني من n من المراحل مع q من المنافذ المتوازية، وتكون الأوزان مستقلة عن العقد (دوال خطية لاختيارات المنافذ). * الرسم (Mapping): يتم رسم مشكلة المسار على التقاطع متعدد الحدود الأمثل (OPI) أو max-LINSAT. هنا، يمثل إيجاد مسار إيجاد متعدد حدود (أو متجه) يلبي أكبر عدد من القيود الخطية (المقاييس) عبر حقل منتهٍ.
الآلية: يستخدم DQI تحويل فورييه الكمي وخطوة فك تشفير (فك تشفير Reed-Solomon لـ OPI) لتحويل المشكلة إلى مهمة فك تشفير. على عكس بحث غروفر، الذي يضخم الحلول الجيدة من تراكب منتظم، يقوم DQI ببناء حالة على جانب المقياس ويستخدم التداخل لتركيز السعة على المسارات التي تلبي العديد من القيود.
المساهمات الرئيسية
تحضير حالة خالٍ من الكيوبتات المساعدة: دائرة مثبتة وصحيحة (US) لتوليد تراكبات منتظمة لمسارات DAG باستخدام ∣E∣ فقط من الكيوبتات (واحد لكل قوس) ودون كيوبتات مساعدة. يثبت المؤلف أن سلاسل المسارات الناتلة تشكل كوداً لكشف الأخطاء بمسافة مرتبطة بمحيط (girth) الرسم البياني.
تقدير الموارد: حساب عدد البوابات لأوراكل غروفر والبحث، بما في ذلك عدد بوابات Toffoli والدورات. بالنسبة لحالة معينة كبيرة (136 كيوبت قوس، 262,144 مسار)، يتطلب البحث حوالي 4.4×105 من بوابات Toffoli.
التحليل المقارن: مقارنة منهجية بين بحث غروفر، والبرمجة الديناميكية، وطريقة "التقاء المنتصف" (meet-in-the-middle)، وأخذ العينات المنتظم عبر 22 حالة.
تطبيق DQI: رسم رسمي لمشكلة MCP إلى OPI/max-LINSAT للأنسجة المتدرجة، مع تحديد الشروط (الأوزان المستقلة عن العقد، الحساب المودولاري) التي ينطبق فيها DQI.
التحقق التجريبي: تنفيذ حالتين ثنائيتين صغيرتين (B1 و B2) على معالجات IBM Heron، جنباً إلى جنب مع محاكاة على مستوى الحالة لحالات OPI الأكبر.
النتائج
أداء بحث غروفر:
المقارنة الكلاسيكية: في الحالات المختبرة (التي تقع في نظام شبه متعدد الحدود)، تتفوق البرمجة الديناميكية الكلاسيكية بشكل كبير على نهج غروفر. بالنسبة لأكبر حالة، تطلبت البرمجة الديناميكية 18,754 تسمية (label)، بينما تطلب بحث غروفر حوالي 4.4×105 من بوابات Toffoli المنطقية.
التحجيم (Scaling): في أسوأ الحالات، تطابق طريقة "التقاء المنتصف" الكلاسيكية أس O(N) الخاص بغروفر. وبينما يوفر غروفر ميزة محتملة قدرها O(N1/4) عندما تكون الحلول كثيفة (M≈N)، فإن هذه الفجوة تتقلص بفعل استراتيجيات "التقاء المنتصف" الكلاسيكية ذات العينات الفرعية على الرسوم البيانية ذات البنية الهيكلية.
الأجهزة: لم يتم إجراء عمليات تشغيل للأجهزة للبحث العام لغروفر؛ النتائج مبنية على محاكاة مثالية وتقديرات الموارد.
أداء DQI:
المحاكاة: أظهرت المحاكاة على مستوى الحالة لست حالات OPI أن DQI يحقق أعداداً متوسطة أعلى من المقاييس المستوفاة مقارنة بأخذ العينات المنتظم والاستكمال الكلاسيكي. على سبيل المثال، في حالة ذات 17 منفذاً و5 مراحل، استوفى DQI نسبة 71.1% من المقاييس في المتوسط، مقارنة بـ 47.1% للمسارات العشوائية.
عمليات الأجهزة: تم تشغيل حالتين ثنائيتين صغيرتين (B1 و B2) على أجهزة IBM.
B1 (5 كيوبت): احتفظت الأجهزة بـ 67% من الربح المثالي مقارنة بأخذ العينات المنتظم.
B2 (11 كيوبت): احتفظت الأجهزة بـ 15% فقط من الربح المثالي.
يعزو المؤلف التدهور أساساً إلى عمق الدائرة والضجيج، مشيراً إلى أن معدل الخطأ الفعلي كان حوالي أربعة أضعاف متوسط خطأ الجهاز.
الأهمية والقيود (ادعاءات المؤلف) تحافظ الورقة على موقف متواضع تجاه ادعاءاتها:
لا توجد ميزة عملية لـ MCP العام: يخلص المؤلف إلى أن بحث غروفر البسيط ليس أفضل خوارزمية كمية معروفة لـ MCP العام. فهو يتفوق عليه بالبرمجة الديناميكية الكلاسيكية في حالات شبه متعددة الحدود، وبالخوارزميات الكمية الأخرى (مثل المشيات الكمية أو التراجع الكمي) التي تستخدم ذاكرة الوصول العشوائي الكمية (QRAM) أو أسساً أفضل.
ميزة DQI غير مثبتة ولكن مدعومة: يتم دعم ميزة DHF للحالة الخاصة (OPI) بالأدلة بدلاً من إثبات رسمي لصعوبة كلاسيكية للمعاملات المستخدمة. تشير الورقة إلى أن الفصل المثبت لـ OPI موجود في نموذج أوراكل لنسخة "مطوية"، وDQI ليس مثالياً لحالات الأسوأ.
نطاق التجارب: اقتصرت تجارب الأجهزة على حالات ثنائية تافهة (max-XORSAT) يمكن حلها بالنظر. يصرح المؤلف صراحة بأن هذه التشغيلات تثبت أن أنماط التداخل تنجو على الأجهزة الحالية ولكنها لا تثبت ميزة حوسبية.
العمل المستقبلي: يحدد المؤلف الحاجة إلى دوائر تحكم للتحقق من آليات التداخل، وإجراء تشغيلات متكررة مع بيانات معايرة كاملة، واختبارات لحالات ذات أوزان كبيرة أو أعداد حلول غير معروفة لتقييم فائدة هذه النهج بشكل كامل.
باختصار، توفر الورقة إطاراً تقنياً صارماً لتطبيق البحث والتداخل الكمي على إيجاد المسارات، لكنها تخلص إلى أنه بالنسبة للحالات والخوارزميات المختبرة، تظل الطرق الكلاسيكية متفوقة في الكفاءة، وتظل المزايا الكمية نظرية أو محدودة بصياغات معينة غير قياسية للمشكلة.