خوارزمية تقريبيّة فعّالة بالبت-الكمومية لمشكلة MaxCut

لماذا تهمّ رقائق الكم الصغيرة في حلّ الألغاز الكبيرة

تختزل العديد من المهام الواقعية—من ترتيب دوائر الحاسوب إلى نمذجة المواد—إلى مسألة فصل شبكة إلى مجموعتين مع قطع أكبر عدد ممكن من الروابط بينهما. هذه المشكلة، المعروفة باسم MaxCut، صعبة للغاية لحواسيب التقليدية. يقدم المقال طريقة جديدة مستوحاة من الكمّ قادرة على التعامل مع شبكات كبيرة بشكل مدهش باستخدام عدد قليل فقط من وحدات الكم (qubits)، ما يوفّر نهجاً جديداً لاختبار وتحسين أدوات التحسين الكمّي والكلاسيكي على حد سواء.

تقطيع الشبكة إلى نصفين مفيدين

تطرح MaxCut سؤالاً يبدو بسيطاً: إذا كان لديك مجموعة نقاط (عُقد) مرتبطة بخطوط (حواف)، كيف تلوّن كل عقدة—مثلاً أزرق أو أبيض—بحيث تكون أكبر عدد ممكن من الخطوط موصولة بين عقدتين مختلفتين اللون؟ هذا التقسيم الأمثل ذو قيمة في مجالات مثل تصميم الدوائر والفيزياء الإحصائية لكنه صعب جداً إيجاده بدقة عندما تكون الشبكة كبيرة. نهج كلاسيكي واسع الانتشار، خوارزمية Goemans–Williamson (GW)، يقوم بتقريب ذكي للمشكلة ويضمن العثور على قطع لا تقل جودته عن نحو 88% من الأفضل الحقيقي. تعد الحوسبة الكمّية بطرق جديدة لمهاجمة مثل هذه المشكلات، لكن الأجهزة الحالية ضوضائية ومحدودة الحجم، مما يجعل تشغيل دوائر عميقة وكبيرة أمراً صعباً.

حلّ الرسوم الكبيرة باستخدام عدد قليل من الكيوبتات

تحتاج النهج الكمّية القياسية مثل خوارزمية التحسين التقريبي الكمّي (QAOA) إلى كيوبت واحد لكل عقدة من الشبكة، لذا فإن رسمًا مكونًا من 1000 عقدة يتطلّب 1000 كيوبت—وهو رقم يفوق قدرة الآلات اليوم. تقلب الطريقة الجديدة، المسماة Qubit-Efficient MaxCut (QEMC)، هذا المقياس رأساً على عقب: فهي تستخدم تقريباً لوغاريتم عدد العقد، إذ يمكن لِـ11 كيوبت أن تشفر معلومات عن أكثر من 2000 عقدة. بدلاً من ربط كل كيوبت بعقدة واحدة، تستخدم QEMC الحالة الكمّية الكاملة كفضاء عناوين مضغوط وتربط عقداً مختلفة بحالات أساس مختلفة لسجل صغير. هذا الاقتصاد في استخدام الكيوبتات يبقي الدوائر ضحلة وأسهل للتشغيل على أجهزة ضوضائية، مع الاحتفاظ بقدرة تمثيل رسوم بيانية كبيرة جداً.

تلوين العقد حسب الاحتمال بدلاً من الحالات الثابتة

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

اختبار الأداء على أجهزة حقيقية ومحاكيات

يختبر المؤلفون QEMC على محوريْن: معالجات كمّية فعلية ومحاكاة كلاسيكية للدوائر الكمّية. على رسوم منتظمة صغيرة تصل إلى 32 عقدة (باستخدام 2 إلى 5 كيوبت فقط)، يجد QEMC المُشغّل على أجهزة IBM الفائقة التوصيل قطوعاً تطابق أو تقترب من أفضل الإجابات الممكنة التي تُستخرج بالبحث الشامل، متفوّقاً بوضوح على التخمين العشوائي والدراسات الكمّية السابقة المبنية على QAOA. في المحاكاة الخالية من الضوضاء، تصل QEMC باستمرار إلى أكثر من 97% من القطع الأمثل لهذه الرسوم الصغيرة. وتبرز قوة الترميز بشكل أكبر للرسوم الأكبر: بالنسبة لرسوم منتظمة من الدرجة 9 تصل إلى 2048 عقدة، تتفوق محاكاة QEMC الكلاسيكية على GW في المتوسط وأفضل القطوع بنسبة عدة بالمئة، وتُرى مزايا مماثلة على رسوم عشوائية مكونة من 128 عقدة بكثافات مختلفة.

السرعة والقيود والوعد المستوحى من الكمّ

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

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

للغير متخصص، الرسالة الرئيسة هي أن الأجهزة الكمّية الصغيرة والضوضائية لا تزال يمكن أن تكون مفيدة علمياً إذا صممنا خوارزميات تتناسب مع نقاط قوتها. من خلال ترميز ألوان العقد في نطاقات احتمالية مرنة بدلاً من قيم بتٍ جامدة، تستخدم QEMC عددًا قليلاً جداً من الكيوبتات لمعالجة مشكلات شبكات كبيرة وتتحمّل الضوضاء المادية طبيعياً. تضع الطريقة معياراً جديداً لاختبار خوارزميات التحسين الكمّي وتُنتج أيضاً خوارزمية كلاسيكية عملية مبنية على نفس الأفكار. وبشكل أوسع، تُظهر كيف أن إعادة التفكير في كيفية ترميز المعلومات—بدلاً من مجرد تصنيع آلات أكبر—يمكن أن تفتح طرقاً واعدة لحلّ مشكلات حسابية صعبة.

الاستشهاد: Tene-Cohen, Y., Kelman, T., Lev, O. et al. A Variational Qubit-Efficient MaxCut Heuristic Algorithm. npj Quantum Inf 12, 50 (2026). https://doi.org/10.1038/s41534-026-01186-2

الكلمات المفتاحية: MaxCut, التحسين الكمّي, الخوارزميات المتغيرة, تقسيم الرسوم البيانية, الحوسبة المستوحاة من الكمّ