Improved quantum volume estimation with transducers and amortized quantum walks

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

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

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

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

باستخدام هذا الإطار، صاغ الفريق نسخة كمومية من "المشي السريع". لقد صمموا نوعًا محددًا من المحولات يمكنه عكس الحالة الكمومية للمشي حول "توزيعه المستقر" (stationary distribution) — وهي الحالة التي يستقر فيها المشي في نمط ثابت. هذا الانعكاس هو المحرك الأساسي للمشي الكمومي. ومن خلال تحليل هندسة الشكل وخصائص المشي بعناية، أثبتوا أن تكلفة هذه الانعكاسات يمكن استهلاكها تدريجيًا (amortized). وهذا يعني أنه على الرغم من أن بعض الخطوات في المشي الكمومي كانت مكلفة نظريًا، إلا أن متوسط التكلفة لكل خطوة ظل منخفضًا. وقد دمجوا ذلك مع تقنيات كمومية أخرى، مثل "التلدين الكمومي" (quantum annealing)، الذي يساعد النظام على الانتقال بسلاسة من حالة إلى أخرى، و"تقدير المتوسط الكمومي" (quantum mean estimation)، الذي يسمح بتقدير دقيق للقيم. والنتيجة هي خوارزمية كاملة لتقدير حجم جسم محدب في مساحة عالية الأبعاد.

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

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

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