💻 computer science

AutoQ 2.0: From Verification of Quantum Circuits to Verification of Quantum Programs (Technical Report)

يُعد AutoQ 2.0 مُحقِّقاً متقدماً يوسع نطاق التحقق من الدوائر الكمومية ليشمل البرامج الكمومية الكاملة عبر معالجة التحديات النظرية والهندسية المتعلقة بالتدفق الكلاسيكي للتحكم، وقد أثبت نجاحه بكفاءة في خوارزميات معقدة مثل "التكرار حتى النجاح" والبحث في خوارزمية "غروفر" القائم على القياس الضعيف.

المؤلفون الأصليون: Yu-Fang Chen, Kai-Min Chung, Min-Hsiu Hsieh, Wei-Jia Huang, Ondřej Lengál, Jyun-Ao Lin, Wei-Lun Tsai

نُشر 2026-05-08

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Yu-Fang Chen, Kai-Min Chung, Min-Hsiu Hsieh, Wei-Jia Huang, Ondřej Lengál, Jyun-Ao Lin, Wei-Lun Tsai

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

الصورة الكبيرة: من المخططات الثابتة إلى الوصفات الديناميكية

تخيل أنك تبني منزلاً.

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

بنى المؤلفون هذه الأداة الجديدة للتحقق من أن هذه البرامج الكمومية المعقدة التي تتخذ القرارات تعمل تماماً كما أراد المبرمج، دون الحاجة إلى تدخل بشري لفحص كل خطوة يدوياً.

التحدي الجوهري: مشكلة "الانهيار"

في العالم الكمومي، هناك قاعدة فريدة: القياس (Measurement).
تخيل أن لديك عملة معدنية تدور وهي في حالة "تراكب" (Superposition)، أي أنها تعتبر "وجه" و"ظهر" في نفس الوقت. اللحظة التي تنظر فيها إليها (تقيسها)، فإنها "تنهار" لتصبح إما وجهاً أو ظهراً.

الصعوبة: في الأدوات القديمة، بمجرد قياس العملة، تصبح الرياضيات معقدة للغاية. كان لا بد من "تطبيع" (Normalize) الاحتمالات (إعادة حسابها بحيث يكون مجموعها 100%)، مما جعل الحسابات الحاسوبية بطيئة وصعبة للغاية.
خدعة AutoQ 2.0: أدرك المؤلفون أنهم ليسوا بحاجة إلى إصلاح الرياضيات فوراً. قرروا ترك الأرقام تصبح "فوضوية" (غير مطبعة) أثناء العملية، والتحقق فقط مما إذا كان شكل النتيجة صحيحاً. لقد بنوا "اختبار استلزام" (Entailment test) خاصاً (أداة مقارنة) يقول: "حتى لو تم تغيير مقياس أرقامك صعوداً أو هبوطاً، طالما أن النمط متطابق، فأنت بخير". هذا يشبه التحقق مما إذا كانت خريطتان تمتلكان نفس الطرق، حتى لو كانت إحدى الخريطتين مرسومة بمقياس 1:100 والأخرى بمقياس 1:1000.

المحرك: "الأوتوماتا الشجرية متزامنة المستويات" (LSTAs)

للتعامل مع هذه البرامج المعقدة، تستخدم الأداة بنية بيانات خاصة تسمى LSTAs.

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

كيف يعمل: الخطوات الثلاث

عندما تريد التحقق من برنامج كمومي باستخدام AutoQ 2.0، فأنت تعمل كمعلم يصحح واجبات الطالب:

الإعداد (الشروط المسبقة - Pre-conditions): تخبر الأداة: "ابدأ بعملة معدنية تدور بهذا الشكل". (هذه هي حالة الإدخال).
الحلقة (الثوابت - Invariants): إذا كان البرنامج يحتوي على حلقة (تعليمات "كرر حتى")، يجب عليك تقديم "ثابت الحلقة" (Loop Invariant).
- التشبيه: تخيل عداءً يركض لافات (دورات). أنت تخبر الأداة: "مهما كان عدد الدورات التي يركضها، فسيظل دائماً على المضمار". لست بحاجة إلى فحص كل خطوة، بل تحتاج فقط إلى إثبات أنه إذا كان على المضمار في بداية اللفة، فسيظل على المضمار في نهايتها.
الهدف (الشروط اللاحقة - Post-conditions): تخبر الأداة: "يجب أن ينتهي البرنامج والعملة تظهر وجهاً".

تقوم الأداة بعد ذلك بتشغيل البرنامج افتراضياً، مستخدمة "نمطها" (LSTA) لتتبع الحالة. وهي تتحقق من:

هل بدأ البرنامج بشكل صحيح؟
هل تحافظ الحلقة على بقاء العداء على المضمار (الثابت)؟
هل انتهى البرنامج والعملة تظهر وجهاً؟

الاختبارات الواقعية: ماذا تحققوا؟

اختبر المؤلفون AutoQ 2.0 على نوعين صعبين جداً من البرامج الكمومية التي لم تستطع الأدوات السابقة التعامل معها تلقائياً:

التكرار حتى النجاح (Repeat-Until-Success - RUS):
- السيناريو: تخيل أنك تحاول خبز كعكة، لكنك لا تعرف ما إذا كان الفرن ساخناً بما يكفي. تضع الكعكة، وتتحقق من درجة الحرارة، وإذا كانت باردة جداً، تخرجها، وتنتظر، وتحاول مرة أخرى. تستمر في التكرار حتى تنضج الكعكة.
- النتيجة: قام AutoQ 2.0 بالتحقق من خوارزميات "المحاولة مرة أخرى" هذه بشكل فوري.
بحث غروفر بالقياس الضعيف (Weak-Measurement Grover's Search):
- السيناريو: خوارزمية غروفر هي طريقة شهيرة لإيجاد إبرة في كومة قش. نسخة "القياس الضعيف" هي طريقة جديدة ومعقدة حيث تلمح كومة القش برفق دون أن تسبب انهياراً كاملاً للموقف فوراً، مما يسمح لك بالاستمرار في البحث حتى لو لم تجد الإبرة على الفور.
- النتيجة: هذا برنامج ضخم. نجح المؤلفون في التحقق من نسخة تحتوي على 100 كيوبت (عدد هائل بالنسبة للحوسبة الكمومية) في حوالي 20 دقيقة. هذا يمثل قفزة هائلة في النطاق عما كان ممكناً سابقاً.

الخلاصة

AutoQ 2.0 هو طفرة لأنه أول أداة يمكنها التحقق تلقائياً من البرامج الكمومية المعقدة التي تستخدم الحلقات واتخاذ القرارات. يقوم بذلك عن طريق استخدام "مطابقة الأنماط" الذكية (LSTAs) لتجنب الغرق في رياضيات مستحيلة، وببراعة في كيفية التعامل مع الرياضيات الفوضوية للقياسات الكمومية.

لقد أثبت بنجاح أن هذه الوصفات الكمومية المتقدمة تعمل بشكل صحيح، حتى للأنظمة الكبيرة جداً، دون الحاجة إلى جهد بشري كبير لإثبات ذلك.

ملخص تقني: AutoQ 2.0: من التحقق من الدوائر الكمومية إلى التحقق من البرامج الكمومية

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

توسع البرامج الكمومية الدوائر الكمومية عبر دمج بنى التحكم الكلاسيكية في التدفق مثل التفرعات والحلقات التكرارية. وبينما تكفي الدوائر الكمومية (مجال AutoQ 1.0) لتحديد تسلسلات ثابتة من البوابات، فإن الخوارزميات الكمومية المتقدمة — مثل خوارزميات "التكرار حتى النجاح" (RUS) ونسخ خوارزمية بحث "غروفر" القائمة على القياس الضعيف — تتطلب تحكماً ديناميكياً بناءً على قيم كلاسيكية مستمدة من قياسات الكيوبتات.

ويفرض التحقق من هذه البرامج تحديات جسيمة لا توجد في التحقق من الدوائر فقط:

القياس والتطبيع (Normalization): يؤدي القياس إلى انهيار الحالات الكمومية ويُنتج قيمًا كلاسيكية (0 أو 1) تقود تدفق التحكم. هذه العملية غالباً ما تتطلب تطبيع سعات الاحتمالية، مما يعقد الاستدلال الصوري.
الاستدلال على تدفق التحكم: يتطلب التحقق من الحلقات والتفرعات التعامل مع فضاءات الحالة التي تتطور بناءً على نتائج القياس، وهي مهمة صعبة بالنسبة للأدوات المؤتمتة الحالية.
نقص الأدوات المؤتمتة: بينما توجد أدوات التحقق الاستنتاجي للبرامج الكلاسيكية (مثل Dafny وKeY)، وتوجد بعض الأدوات الكمومية (مثل CoqQ وQbricks)، إلا أنها إما تفتقر إلى الأتمتة الكاملة أو تتطلب جهداً يدوياً كبيراً (مثل توفير مؤثرات هيرميتية معقدة أو بحث مكثف عن البراهين). تركز الأدوات المؤتمتة الحالية غالباً على تكافؤ الدوائر أو برامج محددة ذات معاملات، وتفتقر إلى الدعم العام لتدفق التحكم في البرامج الكمومية.

2. المنهجية

يعالج AutoQ 2.0 هذه التحديات عبر توسيع إطار التحقق من الدوائر السابق لدعم البرامج الكمومية الكاملة. تعتمد المنهجية الجوهرية على الأوتوماتا الشجرية متزامنة المستويات (LSTAs) ونهج مبتكر لـ اختبار الاستلزام.

2.1 النموذج الصوري: الأوتوماتا الشجرية متزامنة المستويات (LSTAs)

يستخدم الأداة مجموعات الحالات الكمومية (الشروط المسبقة، الشروط اللاحقة، وثوابت الحلقات) باستخدام LSTAs.

البنية: تعد LSTAs أوتوماتا شجرية رمزية مصممة لترميز الحالات الكمومية كأشجار ثنائية كاملة، حيث تمثل الفروع حالات القاعدة الحسابية وتمثل الأوراق سعات الاحتمالية المعقدة.
التزامن: الميزة الرئيسية لـ LSTAs هي آلية "الاختيار". يجب أن تشترك الانتقالات عند نفس المستوى الشجري في مجموعة اختيار مشتركة. يسمح هذا لـ LSTAs بتمثيل الحالات المتشابكة والتراكبات بشكل مدمج، وهو ما لا تستطيع الأوتوماتا الشجرية القياسية فعله، وذلك من خلال ضمان توليد التوليفات الصحيحة فقط من الفروع (التي تشترك في الاختيار).
تنسيق الإدخال: يحدد المستخدمون الشروط المسبقة، الشروط اللاحقة، وثوابت الحلقات كملفات .lsta تُعرف الأوتوماتا التي تتعرف على مجموعات الحالات الكمومية الصالحة.

2.2 إطار التحقق

عملية التحقق مؤتمتة وتتبع أسلوباً استنتاجياً:

تنفيذ البرنامج: تقوم الأداة بتنفيذ البوابات الكمومية (مثل $H, CX, T$ ) على الـ LSTA الذي يمثل الشرط المسبق.
التعامل مع القياس والتفرعات:
- عند حدوث قياس $M_i = b$ ، يتم تقسيم الـ LSTA إلى نسختين تقابلان نتيجتي $b=0$ و $b=1$ .
- تقوم الخوارزمية بتحديث الشجرة عبر تصفير سعات الاحتمالية للفروع غير المتطابقة (على سبيل المثال، إذا كان $M_1=0$ ، يتم ضبط السعات في الشجرة الفرعية لـ $1 $تحت$ x_1$ لتصبح 0).
- بشكل حاسم، لا تقوم الأداة بـ تطبيع السعات خلال هذه الخطوة. فهي تحافظ على السعات الخام لتجنب الحسابات المعقدة أثناء التنفيذ، وتؤجل فحوصات التطبيع إلى اختبار الاستلزام النهائي.
- يتم التعامل مع عبارات التفرع عبر حساب الـ LSTAs الناتجة لكل من المسارين (الصحيح والخاطئ) ثم أخذ اتحادهم.
التعامل مع الحلقات:
- بالنسبة لحلقات while ، يجب على المستخدم تقديم ثابت حلقة (loop invariant) كـ LSTA.
- تتحقق الأداة من أن الثابت استقرائي: يجب أن يغطي جميع الحالات التي يمكن الوصول إليها قبل الحلقة، وأن يؤدي تنفيذ جسم الحلقة على الثابت (بناءً على شرط استمرار الحلقة) إلى حالات لا تزال مغطاة بالثابت.
- يتم تقريب الحالات عند مخرج الحلقة تقريباً علوياً بواسطة الثابت المشروط بانتهاء الحلقة.
اختبار الاستلزام (حتى التدرج/Scaling):
- الخطوة النهائية تتحقق مما إذا كانت مجموعة الحالات الممكن الوصول إليها (الممثلة بـ LSTA يرمز له بـ $R$ ) متضمنة في الشرط اللاحق (LSTA يرمز له بـ $Q$ ).
- نظراً لتجاهل عوامل التطبيع أثناء التنفيذ، تستخدم الأداة علاقة استلزام متخصصة حتى التدرج ( $|=_{uts}$ ).
- يتحقق $A |=_{uts} B$ إذا كانت كل شجرة في $A$ هي نسخة متدرجة خطياً من شجرة في $B$ (أي $T_A = r \cdot T_B$ لقيمة ثابتة غير صفرية $r$ ).
- يتم إجراء هذا الفحص باستخدام خوارزمية بحث في الرسوم البيانية تتنقل عبر مستويات LSTAs، وتربط الحالات والمصطلحات، وتستدعي أخيراً محلل النماذج (SMT solver) وهو Z3 للتحقق من وجود عامل التدرج $r$ الذي يحقق القيود العالمية.

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

التوسع إلى البرامج الكمومية: يعد AutoQ 2.0 أول أداة توفر تحقق استنتاجي مؤتمت للبرامج الكمومية التي تحتوي على حلقات وتفرعات، متجاوزة نطاق الدوائر فقط الذي تميز به AutoQ 1.0.
التعامل المؤتمت مع القياس: تقدم الأداة خوارزميات لتقسيم LSTAs بناءً على نتائج القياس وإدارة فضاءات الحالات الناتجة دون تدخل يدوي.
التحقق الخالي من التطبيع: من خلال تصميم اختبار استلزام يعمل مع الحالات غير المطبعة (حتى التدرج)، تتجنب الأداة التعقيد الحسابي لتطبيع السعات أثناء مرحلة التنفيذ، مما يحسن الكفاءة بشكل كبير.
ثوابت الحلقات القائمة على LSTA: يستخدم الإطار LSTAs لتمثيل ثوابت الحلقات، مما يسمح بالتمثيل المدمج للحالات الكمومية المعقدة المطلوبة للخوارزميات التكرارية.
القابلية للتوسع: يدعم النهج التحقق من البرامج ذات عدد كبير من الكيوبتات (حتى 100 كيوبت في الاختبارات المذكورة) عبر الاستفادة من ضغط LSTAs وكفاءة حل SMT.

4. النتائج التجريبية

قام المؤلفون بتقييم AutoQ 2.0 على فئتين من البرامج الكمومية المتقدمة:

خوارزميات التكرار حتى النجاح (RUS): تُستخدم لتوليد بوابات كمومية غير قياسية (مثل وحدات معينة مثل $(2X + \sqrt{2}Y + Z)/\sqrt{7}$ $(2 X + 2 Y + Z) / 7$ ).
- النتيجة: تم التحقق من جميع اختبارات RUS لحظياً (0.0 ثانية).
بحث غروفر القائم على القياس الضعيف: نسخة من خوارزمية غروفر لا تتطلب معرفة مسبقة بعدد الحلول.
- النتيجة: نجحت الأداة في التحقق من حالات تصل إلى 100 كيوبت (تحديداً 101 كيوبت في الجدول) في حوالي 11 ثانية (لحالة 101 كيوبت) إلى 20 دقيقة (كما ورد في الملخص لحالة 100 كيوبت؛ يبدو أن الملخص يشير إلى تكوين معين أو وقت الإعداد، رغم أن الجدول يظهر 11 ثانية لـ 101 كيوبت). يتوسع وقت التحقق بشكل معقول مع عدد الكيوبتات والبوابات.

أُجريت التجارب على خادم مزود بمعالج AMD EPYC 7742 وذاكرة وصول عشوائي بسعة 1,152 جيجابايت.

5. الأهمية والادعاءات

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

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