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

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

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

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

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

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

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

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

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

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

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