Optimizing QAOA circuit transpilation with parity twine and SWAP network encodings
تقدم هذه الورقة طريقة تعتمد على التخمير المحاكي تعمل على تحسين عملية نقل دوائر خوارزمية التحسين الكمي التقريبي (QAOA) إلى أجهزة كمية ذات تخطيط ثابت، وذلك من خلال تقليل عبء الترميز لسلاسل التواء التكافؤ (parity twine chains) وشبكات التبديل (SWAP networks) بشكل كبير، مما يحقق انخفاضات جوهرية في عمق الدائرة وأعداد البوابات ثنائية الكيوبت مقارنة بالمترجمات القياسية.
المؤلفون الأصليون:J. A. Montanez-Barrera, Yanjun Ji, Michael R. von Spakovsky, David E. Bernal Neira, Kristel Michielsen
تخيل أنك تحاول تنظيم حفلة رقص ضخمة وفوضوية، حيث يحتاج كل ضيف إلى الإمساك بيد كل ضيف آخر في وقت ما لأداء روتين خاص. الآن، تخيل أن ساحة الرقص هي ممر ضيق ذو صف واحد. في هذا الممر، لا يمكن للناس إلا الإمساك بأيدي الأشخاص المجاورين لهم مباشرة. إذا كان على الضيف (أ) أن يمسك بيد الضيف (ز)، الموجود في نهاية الطابور تماماً، فلا يمكنه ببساطة مد يده عبر الحشد؛ بل يتعين عليه التحرك، وتبادل الأماكن، والتسلل عبر الطابور حتى يصبحا جارين. هذا التبدل يستغرق وقتاً، وفي كل مرة يصطدم فيها شخصان ببعضهما لتبادل الأماكن، هناك احتمال أن يتعثرا، أو يفلت أيديهما، أو يفسدا الروتين. في عالم الحوسبة الكمومية، ساحة الرقص هذه هي شريحة كمومية، والضيوف هم جسيمات متناهية الصغر تسمى "الكيوبتات" (qubits)، و"التعثر" هو نوع من الأخطاء التي تفسد العملية الحسابية. يحاول العلماء باستمرار معرفة كيفية جعل هذه الكيوبتات تتواصل مع بعضها البعض بكفاءة دون أن تتعثر ببعضها البعض، خاصة وأن الشرائح الحالية تشبه ذلك الممر الضيق ولا يمكنها ربط الجميع بالجميع بشكل مباشر.
هذه الورقة البحثية تدور حول إيجاد أفضل تصميم لحركات الرقص تلك. ركز الباحثون على خوارزمية محددة تسمى (QAOA)، والتي تُستخدم لحل الألغاز المعقدة مثل إيجاد أفضل طريقة لتقسيم مجموعة من الأشخاص إلى فريقين. ولجعل هذا العمل ممكناً على شريحة أحادية البعد وضيقة، اضطروا إلى استخدام "التحويل البرمجي" (transpilation)، وهو مجرد مصطلح منمق لإعادة ترتيب التعليمات بحيث يمكن للأجهزة فهمها. لقد اختبروا طريقتين رئيسيتين لهذا التبدل: "شبكة التبادل" (SWAP network)، وهي تشبه رقصة خطية منظمة حيث يتحرك الجميع خطوة بخوة، وطريقة أحدث وأكثر تعقيداً تسمى "سلاسل تشابك التكافؤ" (Parity Twine Chains - PTC)، وهي تشبه ترميز معلومات راقصين في حركات شخص واحد لتوفير المساحة. كما ابتكر المؤلفون تقنية "التلدين المحاكى" (simulated annealing) جديدة، وهي تشبه مدرباً ذكياً يعتمد على التجربة والخطأ، يحاول آلاف التشكيلات الأولية المختلفة لإيجاد التشكيلة التي تتطلب أقل قدر من التبدل.
وجد الفريق أنه بالنسبة للألغاز الصغيرة والمتفرقة، كانت برامج الكمبيوتر القياسية المستخدمة من قبل شركات مثل (IBM) جيدة جداً في تقليل عدد الحركات. ومع ذلك، كلما كبرت الألغاز وأصبحت الروابط بين الكيوبتات أكثر تكراراً، بدأت أساليبهم الجديدة في التألق. فمن خلال استخدام مدربهم الذكي لإعادة ترتيب الترتيب الأولي للكيوبتات، استطاعوا تقليل عدد المرات التي تضطر فيها الكيوبتات لتبادل الأماكن بشكل كبير. وفي لغز ضخم يتكون من 120 كيوبت بنسبة اتصال 25%، نجحت طريقتهم في اختصار 87% من عمق الدائرة (الوقت المستغرق للتشغيل) و29% من بوابات الكيوبت الثنائية (الحركات الخطرة) مقارنة ببرمجيات (IBM) القياسية. كما اختبروا ذلك على أجهزة كمومية حقيقية، وتحديداً جهازي "ibm fez" و"ibm kingston". وعلى جهاز "ibm fez"، تمكنوا من إيجاد الحل المثالي لمشكلة مكونة من 20 كيوبت باستخدام طريقة (PTC) الخاصة بهم، بينما لم تنجح الطريقة القياسية إلا حتى 15 كيوبت فقط. ومن المثير للاهتمام أنه على جهاز "ibm kingston"، كان أداء طريقة (SWAP) القياسية أفضل قليلاً من طريقة (PTC) لنوع معين من المشكلات، مما يشير إلى أنه في بعض الأحيان لا يكون امتلاك عدد أقل من الحركات هو الشيء الوحيد المهم؛ بل إن الطريقة التي يتم بها ترميز المعلومات لا تقل أهمية. ويشير الباحثون إلى أنه بينما تعد طريقتهم أداة قوية لتقليل الأخطاء وتوفير الوقت، إلا أنها ليست حلاً سحرياً يعمل بشكل مثالي في كل سيناريو، وأن الخيار الأفضل يعتمد على الشكل المحدد للمشكلة وخصائص الأجهزة المستخدمة.
ملخص تقني: تحسين ترجمة دوائر خوارزمية التحسين التقريبي الكمي (QAOA) باستخدام تشفيرات "Parity Twine" و"SWAP Network"
بيان المشكلة تعاني المعالجات الكمية فائقة التوصيل (QPUs) الحالية من محدودية اتصال الكيوبتات، والتي تقتصر عادةً على الجيران الأقرب ضمن تضاريس محددة (مثل شبكات heavy-hex). يتطلب تنفيذ خوارزميات مثل خوارزمية التحسين التقريبي الكمي (QAOA)، التي تتطلب غالباً تفاعلات كثيفة أو كاملة الاتصال بين الكيوبتات، عملية ترجمة (transpilation). تقوم هذه العملية بخرائط الكيوبتات المنطقية إلى كيوبتات فيزيائية وإدراج بوابات SWAP لتلبية قيود الاتصال. ومع ذلك، يتم تفكيك بوابات SWAP إلى بوابات متعددة من نوع الكيوبت-الثنائي (مثل ثلاث بوابات CNOT)، وهي المصدر الرئيسي للضوضاء والخطأ في الأجهزة الحالية. ورغم أن عمليات التشفير المهيكلة مثل شبكات SWAP وسلاسل Parity Twine Chains (PTC) توفر فوائد تحليلية للموارد في الرسوم البيانية كاملة الاتصال، إلا أن تطبيقها على الرسوم البيانية ضعيفة الاتصال (غير كاملة الاتصال) يظل دون المستوى الأمثل. علاوة على ذلك، فإن إيجاد التعيين الأولي الأمثل للكيوبتات (وهي مسألة تشابه المخططات الفرعية - subgraph isomorphism) لتقليل عدد البوابات في هذه السيناريوهات شحيحة الاتصال هي مسألة معقدة من فئة NP-hard، وتواجه الحلول الموجودة مثل SATMapper قيوداً في القدرة على التوسع وزمن التشغيل.
المنهجية يقترح المؤلفون نهجاً هجيناً يجمع بين استراتيجيات التشفير المهيكلة وخوارزمية التلدين المحاكى (Simulated Annealing - SA) لتحسين التعيين الأولي للكيوبتات من المنطقي إلى الفيزيائي.
التشفيرات:
شبكة SWAP: جدول توجيه مهيكل على سلسلة أحادية البعد (1D chain) حيث تقوم طبقات متبادلة من بوابات SWAP للجيران الأقرب بنقل الكيوبتات المنطقية لخلق التقاربات المطلوبة.
سلاسل Parity Twine Chains (PTC): طريقة لتشفير معلومات Z متعددة الكيوبتات في كيوبتات فيزيائية مفردة عبر التكافؤ (parity). يسمح هذا بتنفيذ التفاعات غير المحلية كدورات أحادية الكيوبت (RZ) محلية، مما يقلل عدد بوابات الكيوبت-الثنائي مقارنة بشبكات SWAP. تستخدم هذه الطريقة استراتيجية فك تشفير حيث يتم أخذ القياسات في أساس التكافؤ، وتتم معالجة النتائج كلاسيكياً لاستعادة السلسلة الثنائية المنطقية، مما يتجنب الحاجة إلى بوابات CNOT إضافية للعودة إلى الأساس الحسابي.
تحسين التلدين المحاكى (SA):
قدم المؤلفون خوارزمية تعتمد على التلدين المحاكى (SA) لحل مسألة تشابه المخططات الفرعية لكل من تشفيرات SWAP وPTC.
دالة التكلفة: دالة التكلفة هي دالة تركيبية وغير سلسة، تقوم بتقييم عدد بوابات الكيوبت-الثنائي التي يمكن تقليمها (إزالتها). وهي تتحقق، طبقة تلو الأخرى، مما إذا كانت أزواج الكيوبتات المعينة تتوافق مع الحواف الأصلية في مخطط الربط الخاص بالأجهزة. إذا كان التفاعل المطلوب غائباً في مخطط المشكلة، يتم حذف البوابات المقابلة في جدول التشفير.
العملية: تقوم الخوارغة بتبديل أزواج تسميات الكيوبتات بشكل متكرر لإيجاد تبديلة (permutation) تقلل إجمالي عدد بوابات الكيوبت-الثنائي وعمق الدائرة. تم اختيار هذا النهج لأن الطرق القائمة على الاشتقاق (gradient-based) غير مناسبة لمساحة البحث المنفصلة، والطرق الدقيقة مكلفة حاسوبياً.
الاختبار المرجعي ونمذجة الضوضاء:
تمت مقارنة الطريقة مع المترجمات القياسية (Qiskit-T, Qiskit-P, Qiskit-AI, TKET) وSATMapper.
تستخدم محاكاة الضوضاء نموذج ضوضاء إزالة الاستقطاب (depolarizing noise model) يعمل على بوابات الكيوبت-الثنائي ضمن بروتوكول Linear Ramp QAOA (LR-QAOA) لمشكلات Weighted MaxCut (WMC).
يتم التحقق التجريبي باستخدام أجهزة IBM الكمية (ibm_fez و ibm_kingston).
المساهمات الرئيسية
تشفيرات محسنة بـ SA: تقديم استراتيجية التلدين المحاكى لتحسين الترتيب الأولي للكيوبتات لكل من تشفيرات PTC وSWAP، مستهدفةً تحديداً الرسوم البيانية جزئية الاتصال.
القابلية للتوسع: إثبات أن نهج SA يتوسع بفعالية مع أعداد الكيوبتات الكبيرة (تصل إلى 200 كيوبت في المحاكاة)، مما يوفر ميزة في زمن التشغيل بمقدار عدة رتب مقدارية عن SATMapper مع تحقيق جودة حل مماثلة.
فك تشفير PTC: وصف تفصيلي لاستراتيجية فك تشفير PTC التي تلغي الحاجة إلى بوابات CNOT التي تزيد من عمق الدائرة للعودة إلى الأساس الحسابي.
التحقق التجريبي: أول تنفيذ تجريبي لتشفير PTC على أجهزة كمية حقيقية.
النتائج
تقليل عدد البوابات والعمق: بالنسبة لدوائر QAOA ذات كثافة الحواف (Ed) التي تتجاوز عتبات معينة، يتفوق PTC+SA وSWAP+SA بشكل كبير على المترجمات القياسية.
بالنسبة لحالة 120 كيوبت بكثافة اتصال 25%، حققت الطريقة المقترحة انخفاضاً بنسبة 87% في عمق الدائرة وانخفاضاً بنسبة 29% في بوابات الكيوبت-الثنائي مقارنة بمترجم Qiskit (مستوى التحسين 3).
العتبة التي يتفوق فيها PTC+SA على Qiskit-T من حيث عدد البوابات تنخفض مع زيادة حجم النظام (من Ed≈0.35 لـ 20 كيوبت إلى Ed≈0.13 لـ 120 كيوبت).
كفاءة زمن التشغيل: تتقارب طريقة SA نحو حلول عالية الجودة في ثوانٍ لمشكلات 200 كيوبت، بينما يتطلب SATMapper مئات إلى آلاف الثواني.
المقاومة للضوضاء:
المحاكاة: أظهر PTC احتمالية نجاح (pgs) أعلى من SWAP في مستويات الضوضاء المنخفضة إلى المتوسطة بسبب قلة البوابات، رغم أن نسبة التقريب (r) ظلت متشابهة لكليهما.
الأجهزة الحقيقية (ibm_fez): وسع تشفير PTC نطاق تجارب LR-QAOA المفيدة. تم العث find الحلول المثلى لأحجام المشكلات حتى 20 كيوبت باستخدام PTC، مقارنة بـ 15 كيوبت فقط باستخدام SWAP. كما استمر التمايز عن العينات العشوائية حتى 22 كيوبت لـ PTC مقابل 20 لـ SWAP.
الأجهزة الحقيقية (ibm_kingston): لمشكلة 20 كيوبت بكثافة Ed=0.298، حقق SWAP+SA أفضل نسبة تقريب (تحسن بنسبة 20.83% عن العينة العشوائية)، متفوقاً على PTC+SA (13.99%). يشير المؤلفون إلى أنه رغم استخدام PTC لبوابات أقل، إلا أن تشفير الأزواج المنطقية في كيوبتات فيزيائية مفردة قد يكون أكثر حساسية لتراكم الضوضاء في سيناريوهات غير كاملة الاتصال.
مقارنة المترجمات: المترجمات القياسية (مثل Qiskit-T) غالباً ما تقلل عدد البوابات على حساب زيادة كبيرة في عمق الدائرة، مما يفاقم تأثير الضوضاء. تحافظ الطرق المقترحة على دوائر مدمجة بعمق أقل.
الأهمية والادعاءات يدعي البحث تقديم أول عرض لتفوق تشفيرات SWAP وPTC على طرق المترجمات القياسية في سيناريوهات الاتصال المنخفض. كما يعد هذا أول تنفيذ تجريبي لتشفير PTC على أجهزة كمية حقيقية.
يؤكد المؤلفون أنه بينما تُعرف التشفيرات المهيكلة المثلى للرسوم البيانية كاملة الاتصال، فإن تطبيقها على الرسوم البيانية جزئية الاتصال عبر تحسين SA المقترح يؤدي إلى تقليل الموارد بشكل كبير. ويخلصون إلى أنه للأنظمة حتى 20 كيوبت، يحسن تشفير PTC الأداء على الأجهزة الحقيقية، مما يمد النطاق الفعال لحجم المشكلات لـ LR-QAOA. ومع ذلك، يشيرون بتواضع إلى أنه في تجارب غير كاملة الاتصال على ibm_kingston، تفوق SWAP+SA أحياناً على PTC+SA، مما يشير إلى أن المقايضة بين عدد البوابات والحساسية للضوضاء تعتمد بشدة على بنية التشفير وتضاريس المشكلة. يضع هذا العمل مساراً عملياً لتنفيذ QAOA على الأجهزة القريبة من المدى (near-term devices) ذات الاتصال المقيد مع تقليل الأعباء الإضافية.