A Quantum Encoding of Traveling Salesperson Tours via Route Generation, Cost Phases, and a Valid-Permutation

إليك ملخص تقني مفصل لورقة البحث بعنوان "ترميز كمي لجولات البائع المتجول عبر توليد المسارات، وأطوار التكلفة، وأوراكل التبديل الصالح" من تأليف ستاتسيك وفوتش.

1. بيان المشكلة

تتناول الورقة البحثية مسألة البائع المتجول (TSP)، وهي مسألة تحسين توافيقي كلاسيكية من فئة NP-hard. الهدف هو إيجاد دورة هاميلتونية ذات تكلفة دنيا في رسم بياني موزون يحتوي على $n$ من المدن، بحيث تزور كل مدينة مرة واحدة بالضبط وتعود إلى نقطة البداية.

• التحدي: ينمو عدد الجولات الصالحة بشكل عامي ($(n-1)!$)، بينما ينمو إجمالي فضاء البحث للمتواليات الممكنة للمدن بشكل أسي ($(n-1)^{n-1}$).
• السياق: بينما توفر الخوارزميات الكمية (مثل خوارزمية غروفر، وQSVT) بحثاً قائماً على التراكب، فإن ترميزات الحواف القياسية (المستخدمة في نماذج QUBO/Ising) غالباً ما تعاني في فرض القيود. تقترح هذه الورقة ترميزاً قائماً على المسار ضمن نموذج دائرة كمية للتعامل صراحة مع بنية التبديل للمسألة.

2. المنهجية: بناء الترميز الكمي

يقترح المؤلفون دائرة كمية مدمجة تقوم بترميز الجولات المرشحة كمتواليات مرتبة زمنياً لملصقات المدن. يتكون البناء من ثلاثة مكونات رئيسية:

أ. تمثيل الحالة (سجل المسار)

• مخطط الترميز: بدلاً من ترميز الحواف، يستخدم الخوارزمية تمثيلاً لسجل الزمن.
  • يتم تثبيت مدينة واحدة (على سبيل المثال، المدينة $n-1$) كنقطة بداية ونهاية.
  • يتم ترميز المدن المتبقية $n-1$ كمتوالية $x_1, x_2, \dots, x_T$ حيث $T = n-1$.
  • يتطلب كل ملصق مدينة $b = \lceil \log_2(n-1) \rceil$ من الكيوبتات.
• عدد الكيوبتات: إجمالي حجم سجل المسار هو $T \times b \approx n \log_2(n)$ كيوبت.
• الحالة الأولية: يتم إنشاء حالة تراكب منتظمة $|\psi_{unif}\rangle$ فوق جميع السلاسل الثنائية الممكنة باستخدام بوابات هادامارد. يمثل هذا جميع المتواليات الممكنة للمدن، بما في ذلك التبديلات غير الصالحة (حيث تتكرر المدن أو تُهمل).

ب. أوراكل الصلاحية ($O_{valid}$)

لتمييز الجولات الصالحة (التبديلات) عن التعيينات غير الصالحة، تم بناء أوراكل عكسي:

• المنطق: تكون الجولة صالحة إذا وفقط إذا ظهر ملصق كل مدينة $i \in \{0, \dots, n-2\}$ مرة واحدة بالضبط في المتوالية.
• التنفيذ:
  1. تراكم التكافؤ (Parity Accumulation): يقوم كيوبت مساعد (ancilla) لكل ملصق مدينة $i \in \{0, \dots, n-2\}$ بتتبع تكافؤ ظهورها عبر جميع الخطوات الزمنية. يتم ذلك عبر مقارنة سجل $|x_t\rangle$ مع الترميز الثنائي لـ $i$ عند كل خطوة، وقلب الكيوبت المساعد المقابل إذا تطابقا.
  2. توليد العلم (Flag Generation): يتم ضبط كيوبت العلم النهائي إلى $|1\rangle$ إذا وفقط إذا أشارت جميع الكيوبتات المساعدة للتكافؤ إلى وجود ظهور واحد فقط (تحديداً، ظهور واحد بالضبط). يتم تحقيق ذلك عبر بوابة MCX متعددة التحكم.
• التعقيد: يتطلب $(n-1)^2$ من بوابات المقارنة وبوابة MCX نهائية واحدة.

ج. أوراكل التكلفة ($O_{cost}$)

يقوم هذا الأوراكل بترميز طول الجولة الإجمالي في طور الحالة الكمية:

• دالة التكلفة: $L(x) = C_{0,x_1} + \sum_{t=1}^{T-1} C_{x_t, x_{t+1}} + C_{x_T, 0}$.
• التنفيذ: يتم تطبيق دورات طور متحكم بها بناءً على أوزان الحواف.
  • حواف البداية والنهاية: يتم التحكم فيها بواسطة ملصقات المدينة الأولى والأخيرة.
  • الحواف المتوسطة: يتم التحكم فيها بواسطة أزواج من ملصقات المدن المتجاورة $(x_t, x_{t+1})$.
• الطور: تتحول الحالة كـ $|x\rangle \to e^{i L(x)/\Lambda}|x\rangle$، حيث $\Lambda$ هو عامل قياس (الحد الأعلى لطول الجولة).

3. المساهمات الرئيسية

1. ترميز مدمج قائم على المسار: تقدم الورقة ترميزاً مباشراً لمتواليات جولات TSP مرتبة زمنياً، مما يجعل بنية التبديل صريحة ويتجنب القيود المعقدة التي غالباً ما تتطلبها الصيغ القائمة على الحواف.
2. تصميم أوراكل معياري: توفر بناءً ملموساً لـ:
   • أوراكل التبديل الصالح الذي يستخدم فحوصات التكافؤ للتحقق من دورات هاميلتون.
   • أوراكل طور التكلفة الذي يراكم أوزان الحواف في طور عالمي.
3. تحليل الموارد: يقدم المؤلفون تحليلاً تقاربياً صارماً لموارد الدائرة المطلوبة لهذه الأوراكل.

4. النتائج وتحليل التعقيد

تحدد الورقة متطلبات الموارد للترميز المقترح:

قيود التضخيم:
يحلل المؤلفون جدوى استخدام تضخيم السعة (خوارزمية غروفر) لإيجاد الجولة المثلى:

• احتمالية النجاح: نسبة الجولات الصالحة في التراكب هي $\frac{(n-1)!}{(n-1)^{n-1}}$. باستخدام تقريب ستيرلينغ، يتقلب هذا كـ $\sim e^{-(n-1)}$.
• النتيجة في التعقيد: عدد التكرارات المطلوبة لتضخيم الفضاء الصالح يتقلب كـ $O(1/\sqrt{p}) \approx O(e^{(n-1)/2})$.
• الاستنتاج: حتى مع وجود تسريع كمي، يظل التعقيد الإجمالي أسياً في $n$ بسبب ضآلة نسبة الحالات الصالحة بشكل أسي. الطريقة لا تنتج خوارزمية زمنية حدودية لمسألة TSP.

5. الأهمية والتوجهات المستقبلية

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

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