⚛️ quantum physics

Evaluating QAOA expectation values can be as hard as counting optimal solutions

تثبت هذه الورقة أن تقييم قيم التوقع لـ QAOA بدقة تامة أو دقة أسية لمسألة MaxCut عند عمق $p \geq 2$ هو مسألة من فئة #P-hard، مما يوضح أن الصعوبة الحسابية تنتقل من القابلية للحل إلى عد الحلول المثلى بدلاً من مجرد التحسين.

المؤلفون الأصليون: Stuart Hadfield

نُشر 2026-08-13

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

CC BY 4.0

المؤلفون الأصليون: Stuart Hadfield

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

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

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

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

رحلة البحث عن الكنز تصبح معقدة

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

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

بالنسبة لالتواء واحد ( $p=1$ )، يكون حساب هذه النتيجة سهلاً؛ يمكنك كتابتها على منديل ورقي. ولكن عندما تضيف التواءً ثانياً ( $p=2$ )، تصبح الأمور غريبة. أظهرت الأبحاث السابقة أن حساب هذه النتيجة كان "NP-hard"، مما يعني أنه كان بصعوبة العثور على ترتيب واحد مثالي للفريق. لكن ورقة هادفيلد تقول: "انتظر، الأمر في الواقع أسوأ من ذلك".

وحش العدّ

اكتشاف هادفيلد الرئيسي هو ترقية حادة في فهمنا لصعوبة الأمر. فهو يثبت أن حساب النتيجة لـ $p \ge 2$ ليس فقط "NP-hard" (إيجاد حل واحد)؛ بل هو #P-hard.

لفهم الفرق، تخيل أنك محقق:

NP-hard تشبه أن يُطلب منك: "هل يمكنك العثور على مشتبه به واحد ارتكب الجريمة؟" إنه أمر صعب، ولكن إذا حالفك الحظ أو حاولت بجدية، فقد تجد واحداً.
#P-hard تشبه أن يُطلب منك: "كم عدد المشتبه بهم إجمالاً الذين ارتكبوا الجريمة؟" يجب عليك العثور على كل واحد منهم وعدّهم.

في عالم علوم الحاسوب، يُعتقد عموماً أن العدّ أصعب بكثير من مجرد العثور على واحد. يوضح هادفيلد أنه بالنسبة لـ QAOA بطبقتين أو أكثر، فإن الرياضيات المطلوبة لحساب النتيجة تجبرك على عدّ العدد الإجمالي للحلول المثالية.

الأداة السحرية

كيف أثبت ذلك؟ بنى هادفيلد "أداة" (gadget) ذكية، وهي تشبه فخاً مصمماً للإيقاع بالحاسوب. لقد أخذ مشكلة MaxCut قياسية وبنى حولها رسماً بيانياً (graph) ضخماً ومعقداً. يحتوي هذا الرسم على نقاط "مرساة" (anchor points) وكتل "متغيرة" (variable blocks).

الخدعة تكمكم في التصميم. عندما يشغل الحاسوب الكمومي رقصته على هذا الرسم البياني المحدد، تتحول النتيجة النهائية (القيمة المتوقعة) إلى تعبير رياضي ضخم يسمى "كثير حدود لوران" (Laurent polynomial). هذا التعبير يشبه سلسلة طويلة من الحدود، كل منها بقوة مختلفة لمتغير (مثل $z^1, z^2, z^3...$ ).

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

لذا، إذا كان بإمكانك حساب نتيجة QAOA لهذا الرسم البياني بسهء، فستعرف فوراً الإجابة على مشكلة "وحش العدّ". وبما أن العدّ يُعتقد أنه مستحيل للحواسيب التقليدية القيام به بكفاءة، فإن حساب نتيجة QAosa يجب أن يكون أيضاً مستحيلاً بالنسبة لها.

مفاجأة "الحافة الواحدة"

تصبح الورقة أكثر إثارة للدهشة. قد تفكر: "حسناً، حساب النتيجة الإجمالية صعب، ولكن رب maybe حساب النتيجة لصداقة واحدة فقط (حافة واحدة) سهل؟"

يقول هافيدلد: لا. هو يثبت أنه حتى لو طلبت من الحاسوب الكمومي فقط أن يخبرك بالارتباط بين شخصين محددين (ارتباط ثنائي الكيوبت مثل $\langle Z_r Z_s \rangle$ )، فإن المشكلة تظل #P-hard. الصعوبة ليست فقط في الصورة الكبيرة؛ بل هي مغروسة في أصغر تفاصيل الخوارزمية.

ماذا يعني هذا للمستقبل

ترسم الورقة خطاً واضحاً في الرمال:

العمق $p=1$ : سهل. يمكننا حساب النتيجة بكفاءة.
العمق $p \ge 2$ : صعب. حساب النتيجة هو بصعوبة عدّ جميع الحلول المثلى.

هذا له تداعيات هائلة. تستخدم العديد من الخوارزميات الحديثة QAOA لتدريب الآلة، وتعديل "الالتواءات" (المعلمات) للحصول على نتيجة أفضل. إذا كان حساب النتيجة بهذا القدر من الصعوبة، فإن تدريب هذه الخوارزميات على حاسوب تقليدي (لمعرفة مدى جودة أداء الآلة الكمومية) قد يكون مستحيلاً للدوائر العميقة.

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

الخلاصة

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

ملخص تقني: تقييم قيم التوقع لـ QAOA هو مسألة من فئة #P-Hard

بيان المشكلة
تتناول الورقة التعقيد الحسابي لتقييم قيم التوقع لخوارزمية التحسين التقريبي الكمي (QAOA) المطبقة على مسألة الحد الأقصى للقطع (MaxCut). وبينما يُعرف أن تقييم قيمة توقع التكلفة $F_p(G; \gamma, \beta) = \langle \psi_p | C_G | \psi_p \rangle$ هو أمر قابل للحساب بكفاءة للعمق $p=1$ على الرسوم البيانية التعميمية، فقد أثبتت أعمال حديثة أن التقييم الدقيق يصبح مسألة صعبة من نوع NP-hard لأي عمق ثابت $p \ge 2$ . السؤال المركزي الذي يتم استقصاؤه هنا هو ما إذا كانت الصعوبة عند $p \ge 2$ تقتصر على التحسين (إيجاد حل) أم تمتد إلى العد (تحديد عدد الحلول المثلى). وتتساءل الورقة عما إذا كان حساب قيم التوقع هذه هو مسألة من فئة #P-hard، وهي فئة تعقيد يُعتقد عموماً أنها أصعب من NP، وتتوافق مع صعوبة عد عدد الحلول لمسألة إرضاء القيود.

المنهجية
يقوم المؤلف بتنقيح آلية إثبات الصعوبة التي قدمها Wang وآخرون [5]، والتي استخدمت كثيرات حدود لورنت (Laurent polynomials) لاستعادة قيمة الحد الأقصى للقطع من أكبر أس. تتضمن منهجية المؤلف الخطوات التالية:

بناء الرسم البياني (أداة العد المتوازن): بدلاً من الأدوات غير المتماثلة المستخدمة في العمل السابق، يقوم المؤلف ببناء رسم بياني محدد $G(H)$ من رسم بياني مدخل $H$ . يعتمد هذا البناء على:
- أدوات المتغيرات (Variable Gadgets): لكل رأس في $H$ ، يتم إنشاء رسم بياني ثنائي التجزئة كامل ومتوازن $K_{L,L}$ ، حيث $L = O(n)$ .
- الحواف المتزامنة (Synchronous Edges): حواف تربط الرؤوس المتقابلة في أدوات $K_{L,L}$ للرؤوس المتجاورة في $H$ للحفاظ على بنية الرسم الأصلي.
- رؤوس الارتكاز (Anchor Vertices): رأسان كليان، $r$ و $s$ ، متصلان بكل رأس في أدوات المتغيرات وببعضهما البعض.
  يضمن هذا البناء أن الرسم البياني $G(H)$ له قطر يساوي 2، وأن قطعاته القصوى مقيدة بصرامة: يجب قطع أدوات $K_{L,L}$ بالكامل، ويجب أن يكون رأسا الارتكاز في جانبين متقابلين.
تحليل كثيرات حدود لورنت: يتم التعبير عن توقع التكلفة (أو مسبب ارتباط ثنائي الكيوبت محدد $\langle Z_r Z_s \rangle$ ) ككثيرة حدود لورنت في متغير الطور $z = e^{i\phi}$ . يحلل المؤلف معاملات هذه الكثيرة الحدود:
- حدد "معاملاً أقصى" (extreme coefficient) يقابل أعلى أس درجة $D^*$ .
- من خلال "تحليل مجموع المسارات المختزل"، يثبت المؤلف أن المعامل $a_{D^*}$ غير صفري ويتناسب طردياً مع عدد القطوع القصوى للرسم البياني الأصلي $H$ .
- تحديداً، $a_{D^*} = \kappa \cdot |\# \text{MC}(H)|$ ، حيث $\kappa$ هو عامل جبري معلوم غير صفري يعتمد على زوايا الخلط وحجم الرسم البياني.
الاختزال عبر الاستيفاء (Reduction via Interpolation): يوضح المؤلف أنه من خلال الاستعلام من أوراكل (oracle) قيمة توقع QAOA عند عدد حدود من قيم الطور المختلفة (جذور الوحدة)، يمكن استخدام تحويل فوريه المتقطع العكسي لاستعادة معاملات لورنت بدقة. وبما أن المعامل الأقصى يشفر عدد القطوع القصوى، فإن وجود أوراكل قادر على التقييم الدقيق (أو التقييم بدقة أسية) يسمح باستعادة هذا العدد، مما يؤدي إلى إنشاء اختزال تورينج حتمي في وقت حدودي من مسألة عد القطوع القصوى (وهي مسألة #P-hard) إلى مسألة تقييم توقعات QAOA.

المساهمات والنتائج الرئيسية

ثنائية التعقيد (Complexity Dichotomy): تثبت الورقة انتقالاً حاداً في التعقيد لقيم توقع QAOA على الرسوم البيانية البسيطة غير الموزونة:
- $p=1$ : المسألة تنتمي إلى الفئة FP (قابلة للحساب في وقت حدودي).
- $p \ge 2$ : المسألة هي #P-hard بموجب اختزالات تورينج الحتمية في وقت حدودي.
العد مقابل التحسين: على عكس نتيجة NP-hardness التي استعادت قيمة الحد الأقصى للقطع، يظهر هذا العمل أن تقييم قيمة التوقع يسمح باستعادة عدد القطوع القصوى. وهذا يرفع مستوى الصعوبة من التحسين إلى العد.
صعوبة مقيدة: تظل صرامة #P-hardness قائمة حتى تحت قيود كبيرة:
- تنطبق على تقييم مسبب ارتباط ثنائي الكيوبت واحد محدد $\langle Z_r Z_s \rangle$ بدلاً من دالة التكلفة الشاملة.
- تنطبق على مجموعة مقيدة للغاية من بارامترات الخوارزمية (زوايا خلط ثابتة $\beta_1 = \arctan(1/2)$ ، $\beta_2 = \pi/4$ ، وزوايا تكلفة مرتبطة $\gamma_1 = \gamma_2 = \phi$ ).
- تنطبق على الرسوم البيانية ذات القطر 2 (رغم أن هذه الرسوم ذات درجات عالية).
المشتقات والمصفوفات الهيسية (Derivatives and Hessians): يوسع المؤلف هذه النتائج ليظهر أن حساب التدرجات والمصفوفات الهيسية الدقيقة لدالة تكلفة QAOA بالنسبة للبارامترات هو أيضاً مسألة #P-hard.
الدقة الأسية: تمتد الصعوبة لتشمل مسألة تقريب قيمة التوقع بخطأ إضافي ضئيل أسياً ( $2^{-\alpha N}$ )، حيث أن هذه الدقة كافية لتمييز المعامل الأقصى واستعادة العدد الصحيح عبر التقريب.

الأهمية والادعاءات
تدعي الورقة أنها تقدم "تصنيفاً دقيقاً وواضحاً للتعقيد" لقيم توقع QAOA. تكمن الأهمية الأساسية في إظهار أن الانتقال من $p=1$ إلى $p=2$ ليس مجرد انتقال من القابلية للحساب إلى صعوبة التحسين (NP-hard)، بل هو انتقال إلى صعوبة العد (#P-hard).

يؤكد المؤلف أن نتائجهم هي عبارات تتعلق بالحالة الأسوأ (worst-case) لعائلات محددة من الرسوم البيانية عالية الدرجة، ولا تعني أن تقييم QAOA صعب لجميع الرسوم البيانية أو الحالات النموذجية. كما يشير إلى أن الصعوبة تعتمد على التقييم الدقيق أو التقييم بدقة أسية؛ وهم لا يدعون الصعوبة في حالات الخطأ الإضافي الثابت أو الضئيل حدودياً، وهي الحالات الأكثر صلة بأجهزة الحوسبة الكمية ذات الضجيج المتوسط (NISQ) الحالية.

علاً عن ذلك، تميز الورقة بين نتائجها وبين نتائج التفوق الكمي المتعلقة بالمعاينة (sampling). فبينما قد تكون المعاينة من مخرجات QAOA عند $p=1$ صعبة كلاسيكياً في ظل ظروف معينة، فإن هذا العمل يظهر أن تقييم قيمة التوقع عند $p=2$ كافٍ لحل مسائل العد من فئة #P-hard. ويخلص المؤلف إلى أن نتائجهم تعني أنه إذا أمكن تقييم توقعات QAOA بكفاءة وبدقة أسية، فإن التسلسل الهرمي متعدد الحدود سيتقلص إلى أدنى مستوياته ( $P=PH$ ). ولهذا تداعيات على الخوارزميات الهجينة التي تعتمد على المعالجة الكلاسيكية لتوقعات كمية، مما يشير إلى أن هذه النهج قد تواجه عوائق حسابية جوهرية في الحالة الأسوأ إذا كانت الدقة العالية مطلوبة.