A quantum lower bound for path finding in welded trees

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

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

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

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

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

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

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