⚛️ الفيزياء الكمومية

A Grover-Amplified Oracle for Maximum Clique on Graph, Minimum Hitting set and Dualizations on Hypergraphs Built on Quantum Phase Estimation

تقدم هذه الورقة إطار عمل لدارات كمومية يستخدم مشغلات ترميز الرسم البياني والترسيم الفائق لبناء أوراكل مُعزز بخوارزمية غروفر لمسألتي "الكلِق الأقصى" (Maximum Clique) و"مجموعة الضرب الأدنى" (Minimum Hitting Set)، والتي تحقق كفاءة فائقة في استهلاك المساحة عبر اشتراط $O(N)$ فقط من الكيوبتات، حتى بالنسبة للرسوم البيانية الفائقة ذات الحواف العددية الأسية، مع تمكين حل مسألة الثنائية للدوال البولينية الموجبة أيضاً.

المؤلف الأصلي: Francisco Piñero, Fernando L. \Pelayo, Hernan I. de la Cruz, Jose J. Paulet, Mauro Mezzini, Fernando Cuartero

نُشر 2026-11-10

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

CC BY 4.0

المؤلف الأصلي: Francisco Piñero, Fernando L. \Pelayo, Hernan I. de la Cruz, Jose J. Paulet, Mauro Mezzini, Fernando Cuartero

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

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

لقد طور فريق من الباحثين طريقة جديدة لمعالجة هذه المشكلات باستخدام نوع محدد من الخوارزميات الكمومية يُعرف باسم "بحث غروفر" (Grover's search). ويقدم عملهم طريقة ذكية لبناء "أوراكل كمومي" (quantum oracle)، يعمل بمثيابة مرشح متخصص يمكنه تحديد الإجابات الصحيحة بسرعة من بين مليارات الإجابات الخاطئة. ويكمن الابتكار الرئيسي في كيفية تخزين المعلومات حول الشبكة؛ فبدلاً من استخدام فتحة ذاكرة منفصلة لكل اتصال أو مجموعة، مما يتطلب مساحة هائلة، يقومون بتشفير الهيكل الكامل للشبكة في "طور" (phase) أو توقيت الحالات الكمومية. يسمح هذا النهج بحل المشكلة باستخدام عدد من الكيوبتات (البتات الكمومية) ينمو فقط بالتناسب المباشر مع عدد العناصر في الشبكة، بدلاً من النمو مع عدد الاتصالات بينها. وهذا يمثل تقليصاً كبيراً في الموارد الفيزيائية المطلوبة، مما يجعل هذا النهج أكثر كفاءة بكثير من الطرق السابقة التي كانت تعاني عندما تصبح الشبكات كبيرة أو معقدة.

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

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

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

كما اكتشف الباحثون أن دائرتهم الخاصة بمشكلة الرسوم البيانية الفائقة لها استخدام ثانوي. فمن خلال قياس توقيت الإشارات دون محاولة إيجاد حل محدد، يمكن للدائرة تقدير العدد الإجمالي للمجموعات الصالحة التي تغطي جميع الاتصالات. وهذه القدرة تحل مباشرة مسألة رياضية تُعرف باسم "ثنائية الدوال البوليانية الموجبة" (dualization of positive Boolean functions)، وهي مهمة في المنطق وتصميم الدوائر. وبينما يقتصر العمل الحالي على عمليات المحاكاة، يشير المؤلفون إلى أن الطريقة تعتمد على التوقيت الدقيق للإشارات الكمومية، وهو متطلب يجب استيفاؤه بواسطة أجهزة كمومية أكثر تقدماً في المستقبل. ومع ذلك، يوفر هذا العمل مخططاً واضحاً لكيفية بناء هذه الـ "أوراكل" الفعالة، ويثبت أنه من الممكن حل هذه المشكلات التوافقية الصعبة بموارد أقل بكثير مما كان يُعتقد سابقاً أنه ممكن.

ملخص تقني: أوراكل تعزيز غروفر لـ "الكلِقة القصوى" و"أصغر مجموعة ضرب" عبر تقدير الطور الكمي

بيان المشكلة
تتناول الورقة مشكلتين أساسيتين من مسائل التحسين التوافقي ذات التعقيد الحسابي (NP-hard): مشكلة الكلِقة القصوى (Maximum Clique Problem - MCP) في الرسوم البيانية، ومشكلة أصغر مجموعة ضرب (Minimum Hitting Set Problem - MHSP) في الرسوم البيانية الفائقة (Hypergraphs). تسعى مشكلة MCP إلى إيجاد أكبر مجموعة فرعية من الرؤوس المترابطة ثنائياً في الرسم البياني $G$ ، بينما تسعى مشكلة MHSP إلى إيجاد أصغر مجموعة فرعية من الرؤوس التي تتقاطع مع كل حافة فائقة في الرسم البياني الفائق $H$ . تعد هذه المشكلات مركزية في مجالات تتراوح من البيولوجيا الحسابية إلى الأمن السيبراني.

تواجه النهج الكمية الحالية، لا سيما تلك القائمة على خوارزمية غروفر، تحديات كبيرة تتعلق بـ التعقيد المكاني (Space Complexity). تتطلب "الأوراكل" (Oracles) التقليدية في نموذج البوابات (Gate-model) لمشكلة MCP عادةً $O(N^2)$ من الكيوبتات (حيث $N$ هو عدد الرؤوس) للتحقق صراحةً من الترابط الثنائي أو لتخزين معلومات الحواف؛ أما بالنسبة للرسوم البيانية الفائقة، حيث يمكن أن يكون عدد الحواف الفائقة $M$ أسياً في $N$ ( $M \in O(2^N)$ )، فإن النهج القياسية التي تتطلب كيوبت مساعداً لكل حافة فائقة تصبح غير مجدية.

المنهجية
يقترح المؤلفون بناءً مبتكراً لأوراكل غروفر يعتمد على تقدير الطور الكمي (Quantum Phase Estimation - QPE) ومشغلي ترميز محددين: مشغل ترميز الرسم البياني (GEO) ومشغل ترميز الرسم البياني الفائق (HEO).

مشغل ترميز الرسم البياني (GEO) لـ MCP:

بدلاً من التحقق من الحواف صراحة، يستخدم المؤلفون الرسم البياني المتمم $\bar{G}$ . المجموعة الفرعية $S$ هي "كلِقة" في $G$ إذا وفقط إذا أنتجت رسماً بيانياً فارغاً في $\bar{G}$ (أي صفر حواف).
يتم تطبيق الـ GEO، المعرف أصلاً في ورقة مرافقة [26] كمتغير ثابت لتناظر الرسم البياني، على $\ـ{\bar{G}}$ . يقوم الـ GEO بحساب عدد الحواف المستحثة بواسطة مجموعة رؤوس فرعية $S$ وتشفير هذا العدد في طور (Phase) حالة القاعدة الحسابية $|x\rangle$ .
بناء الأوراكل:
- سجل الطور (Phase Register): يتم إجراء عملية QPE على الـ GEO لاستخراج عدد الحواف $|E(\bar{G}_S)|$ في سجل طور.
- سجل الوزن (Weight Register): يُستخدم سجل منفصل، مُحمل مسبقاً بالقيمة $-k$ (في نظام المتمم الثنائي)، للتحقق مما إذا كان حجم المجموعة $|S| \geq k$ . تقوم عمليات الزيادة المحكومة بتحديث هذا السجل بناءً على بتات $|x\rangle$ .
- التمييز (Flagging): إذا أشار سجل الطور إلى وجود صفر حواف (مما يعني أن $S$ هي كلِقة في $G$ ) وَأشار البت الأكثر أهمية (MSB) في سجل الوزن إلى أن $|S| \geq k$ ، يتم تطبيق قلب للطور لتمييز الحالة لعملية تعزيز غروفر.
كفاءة المساحة: يستخدم الدائرة $N$ من الكيوبتات لسجل الرؤوس، و $\lceil \log_2 |E(\bar{G})| \rceil + 1$ لسجل الطور، و $\lceil \log_2 N \rceil + 1$ لسجل الوزن. وبما أن $|E(\bar{G})| \leq N(N-1)/2$ ، فإن إجمالي عدد الكيوبتات هو $O(N)$ .

مشغل ترميز الرسم البياني الفائق (HEO) لـ MHSP:

تم تصميم HEO لحساب عدد الحواف الفائقة التي تغطيها المجموعة الفرعية $S$ . المجموعة الفرعية هي "مجموعة ضرب" إذا كانت تغطي جميع الحواف $M$ .
الآلية: يستخدم المشغل مبدأ الاستبعاد والاحتواء المنفذ عبر بوابات الطور.
- الخطوة 1: تضيف بوابات الطور غير المحكومة طوراً يتناسب مع درجة كل رأس (عدد الحواف الفائقة المتصلة به).
- الخطوة 2: تطرح بوابات الطور متعددة التحكم الأطوار الناتجة عن التقاطعات المكررة. تحديداً، للحافة الفائقة $E$ ، إذا تقاطعت المجموعة $S$ مع $E$ في $k$ من الرؤوس، يضمن البناء أن مساهمة الطور الصافية تقابل بالضبط حافة فائقة واحدة مغطاة (بدلاً من $k$ ).
بناء الأوراكل: يشبه الـ GEO، يُستخدم QPE لاستخراج عدد الحواف الفائقة المغطاة. يتم تطبيق إزاحة طور عالمية قدرها $-|E(H)|\theta$ بحيث تؤدي "مجموعة الضرب" (التي تغطي جميع الحواف) إلى طور صافٍ يساوي 0. يتحقق سجل الوزن مما إذا كان $|S| \leq k$ .
كفاء% المساحة: يتطلب HEO عدد $N$ من الكيوبتات للرؤوس وسجلاً للطور بحجم $\lceil \log_2 M \rceil$ . وحتى لو كان $M \in O(2^N)$ ، فإن إجمالي متطلبات الكيوبتات يظل $O(N)$ لأن $\log(2^N) = N$ .

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

تعقيد مساحة خطي: المساهمة الأساسية هي تقليل متطلبات الكيوبت لأوراكل MCP وMHSP القائمة على غروفر من $O(N^2)$ (أو $O(M)$ للرسوم البيانية الفائقة) إلى $O(N)$ . ويتحقق ذلك من خلال تشفير المعلومات الهيكلية (أعداد الحواف/الحواف الفائقة) في طور الحالة بدلاً من استخدام كيوبتات مساعدة للتخزين الصريح أو التحقق.
القابلية للتوسع للرسوم البيانية الفائقة: يسمح HEO بحل مشكلة MHSP في الرسوم البيانية الفائقة ذات عدد أسي من الحواف ( $M \in O(2^N)$ ) باستخدام عدد خطي فقط من الكيوبتات، وهو إنجاز لم يكن ممكناً سابقاً في أوراكل غروفر ذات النموذج البوابي.
ثنائية الدوال البوليانية (Dualization of Boolean Functions): توضح الورقة أن قياس سجل QPE الخاص بـ HEO تحت حالة التراكب الموحد يسمح بـ تقريب عدد مجموعات الضرب. وبما أن إيجاد العدد الدقيق لمجموعات الضرب يحل مباشرة مشكلة الثنائية (dualization problem) للدوال البوليانية الممثلة في الصيغة الطبيعية المشتملة الموجبة (PIDNF)، فإن هذه القدرة توفر نهجاً كمياً لمعالجة مشكلة الثنائية.
تحليل تعقيد البوابات: يقدم المؤلفون تحليلاً مفصلاً يوضح أنه بينما التعقيد المكاني خطي، فإن تعقيد البوابات لكل استدعاء أوراكل هو $O(|E(\bar{G})| \log |E(\bar{G})| + N \log N)$ للرسوم البيانية و $O(MN^2 \log M)$ للرسوم البيانية الفائقة. ويشيرون إلى أنه بالنسبة للرسوم البيانية الكثيفة $G$ ، فإن المتمم $\bar{G}$ يكون متفرقاً (sparse)، مما يجعل GEO فعالاً من الناحية العملية.

النتائج والتحقق

المحاكاة العددية: قام المؤلفون بتنفيذ خوارزمية غروفر الكاملة باستخدام Qiskit وAerSimulator.
- الرسوم البيانية: تم اختبارها على رسوم بيانية تتراوح من $N=5$ إلى $N=10$ . أكدت المحاكاة أن تسلسل "الحساب-التمييز-إلغاء الحساب" (compute-mark-uncompute) يقوم بشكل صحيح بتعزيز حالات الكلِقة المستهدفة، محققاً احتمالات نجاح تتراوح بين 99.5% و100% عند العدد الأمثل نظرياً من التكرارات.
- الرسوم البيانية الفائقة: تم التحقق من أن بناء HEO يقوم بتشفير عدد الحواف الفائقة المغطاة بشكل صحيح، حيث يعمل إلغاء الطور كما هو متوقع لتحديد مجموعات الضرب.
المقارنة: تقارن الورقة تعقيد المساحة $O(N)$ الخاص بها مع الخوارزميات الموجودة (مثل Haverly وLópez، وSanyal et al.، وHan et al.) التي تتطلب $O(N^2)$ من الكيوبتات. ويلاحظ المؤلفون أنه بينما يضحي نهجهم بالمساحة مقابل عمق الدائرة ودقة الطور، فإنه يقدم ميزة كبيرة في عدد الكيوبتات، وهو العائق الرئيسي الحالي أمام الأجهزة الكمية القريبة من العصر الحالي.

الأهمية والادعاءات
تدعي الورقة أن الخوارزميات المقترحة تتفوق على جميع خوارزميات غروفر الكمية السابقة لمشكلتي الكلِقة القصوى وأصغر مجموعة ضرب من حيث التعقيد الحسابي للمساحة.

من خلال اشتراط $O(N)$ فقط من الكيوبتات، تجعل هذه الطريقة مشكلتي MCP وMHSP قابلة للحل على المحاكيات الكمية وعلى الأجهزة المستقبلية المحتملة لقيم $N$ أكبر مما كان ممكناً سابقاً.
تبرز القدرة على التعامل مع الرسوم البيانية الفائقة ذات الحواف الأسية باستخدام كيوبتات خطية كقدرة فريدة، مما يتيح تقريب عدد مجموعات الضرب، وهي الخطوة الرئيسية لحل مشكلة الثنائية للدوال البوليانية الموجبة في سياق كمي.
يقر المؤلفون بتواضع بأن نهجهم يعتمد على دورات طور عالية الدقة (خاصة للرسوم البيانية الفائقة حيث $M \in O(2^N)$ )، مما ينقل عبء التعقيد من عدد الكيوبتات إلى دقة البوابات وعمق الدائرة، وهو مقايضة ذات صلة بالحوسبة الكمية المتسامحة مع الأخطاء (fault-tolerant).

لا تدعي الورقة تحقيق تسريع فوق-متعدد (super-polynomial speedup) مقارنة بالخوارزميات الكلاسيكية (إذ تظل MCP مسألة NP-hard)، بل تدعي تحقيق تسريع تربيعي (quadratic speedup) فوق البحث الكلاسيكي الشامل عبر تكرار غروفر، وذلك باستخدام بصمة موارد أكثر كفاءة بشكل ملحوظ.

أبحاث مشابهة