Linear-depth quantum oracles for clique problems from edge colorings and graph states, with linear non-Clifford cost and a provably bounded-error k-clique search

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

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

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

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

ولضمان دقة البحث، كان على الفريق حل مشكلة معقدة: الطريقة الجديدة لا تعمل كمفتاح تشغيل/إيقاف مثالي. فبدلاً من تحديد "الكليك" فورًا كـ "موجود" وغير "الكليك" كـ "غير موجود"، تنتج الدائرة إشارة دقيقة تكون قوية للمجموعات المتماسكة (cliques) وضعيفة لكل ما سواها. ولتحويل هذه الإشارة الدقيقة إلى نتيجة موثوقة، أضاف الباحثون خطوة تصفية باستخدام تقنية تسمى "تقدير الطور" (phase estimation). تعمل هذه التق التقنية مثل شوكة رنانة، حيث تضخم الإشارة الصحيحة بينما تثبط الضجيج. وقد أثبتوا رياضيًا أن هذا المرشح يضمن عدم تفويت أي "كليك" حقيقي، بينما تظل فرصة تحديد مجموعة غير متماسكة على أنها "كليك" منخفضة للغاية. وفي عمليات المحاكاة الخاصة بهم، تم حصر معدل الخطأ هذا في جزء ضئيل جدًا، مما يضمن قوة البحث.

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

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

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