Quantum Advantage of Permutation-Invariant Functions in Communication Complexity

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

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

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

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

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

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

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

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