A provable quantum advantage for approximate optimization via decoded quantum interferometry
تثبت هذه الورقة وجود ميزة كمومية صارمة للتحسين التقريبي من خلال إثبات أن إطار تداخل الكم المشفّر (DQI)، ولا سيما في شكله المعدل، يحقق نسب تقريب أعلى بكثير في مشكلة تقاطع الحدوديات المثلى المطوية مما يمكن لأي خوارزمية كلاسيكية تعمل في زمن حدودي أن تحققه في بيئة أوراكل (oracle setting).
البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
يُعد التحسين الحسابي فن إيجاد أفضل حل ممكن من بين بحر شاسع من الاحتمالات، وهي مهمة تشكل حجر الزاوال في كل شيء، بدءاً من اللوجستيات والتمويل وصولاً إلى اكتشاف الأدوية والذكاء الاصطناعي. ولعقود من الزمن، تساءل العلماء عما إذا كانت الحواسيب الكمومية، التي تسخر القوانين الغريبة للفيزياء لمعالجة المعلومات بطرق لا تستطيع الآلات الكلاسيكية القيام بها، قادرة على حل هذه المشكلات بشكل أسرع أو أفضل بكثير. وبينما أظهرت الأجهزة الكمومية وعوداً في مهام محددة وضيقة، ظل إثبات امتلاكها لميزة حقيقية لا تقبل الجدل في مشكلات التحسين الواسعة أمراً بعيد المنال. وتكمن الصعوبة في التمييز بين آلة سريعة فحسب، وآلة قادرة جوهرياً على الوصول إلى إجابات لا تستطيع الحواسيب الكلاسيكية العثور عليها ببساطة ضمن إطار زمني معقول. ولحسم هذا الأمر، غالباً ما يلجأ الباحثون إلى نماذج نظرية حيث يمكنهم مقارنة النوعين من الآلات بدقة، مع تجريد العملية من الضجيج الواقعي لرؤية القوة الخام لخواروارزمياتها.
في دراسة جديدة، نجح فريق من الباحثين في إرساء فصل واضح ومثبت بين الأداء الكمومي والكلاسيكي لفئة معينة من مشكلات التحسين. لقد ركزوا على سيناريو يتعين فيه على الحاسوب إيجاد دالة متعددة الحدود تناسب مجموعة من القواعد المخفية والعشوائية بأفضل شكل ممكن. تخيل لغزاً حيث يجب عليك اختيار منحنى يمر عبر أكبر عدد ممكن من المناطق "المسموح بها"، ولكن لا يمكنك معرفة ما إذا كانت نقطة ما مسموحة إلا من خلال طرح سؤال (نعم أو لا) على "عراف" غامض. قام الباحثون ببناء عائلة من هذه الألغاز باستخدام بنية رياضية تُعرف باسم أكواد "ريد-سولومون" المطوية (folded Reed-Solomon codes)، وهي في الأساس قوائم منظمة للغاية من الأرقام ذات الفائض المدمج. وفي إعدادهم، تم اختيار القواعد التي تحدد ما يُعتبر منطقة "مسموح بها" عشوائياً، بحيث يكون نصف جميع الخيارات الممكنة صحيحاً لكل جزء من اللجوز. وقد خلق هذا الإعداد المتوازن خطاً فاصلاً حاداً: حيث يمكن لحاسوب كلاسيكي يستخدم أفضل استراتيجية معروفة أن يحل حوالي 65 بالمائة من قطع اللغز بشكل موثوق، لكن تجاوز هذا الحد تطلب وقتاً وجهداً مستحيلاً.
ثم طبق الباحثون تقنية تسمى "التداخل الكمومي لفك الترميز" (decoded quantum interferometry) على نفس المشكلة. تعمل هذه الطريقة عن طريق تحويل مهمة التحسين إلى مشكلة فك ترميز لكود رياضي ذي صلة. وبدلاً من فحص الخيارات واحداً تلو الآخر، تقوم الخوارزمية الكمومية بإنشاء حالة تراكب للعديد من الاحتمالات وتستخدم التداخل لتضخيم الإجابات الصحيحة مع إلغاء الإجابات الخاطئة. وتثبت الدراسة أن هذا النهج الكمومي يحقق باستمرار درجة تقارب 85 بالمائة في هذه الألغاز العشوائية. والأهم من ذلك، أظهر المؤلفون أنه لكي يتجاوز أي حاسوب كلاسيكي حد الـ 65 بالمائة بمعدل نجاح موثوق، فإنه سيحتاج إلى طرح أسئلة أكثر من عدد الذرات في الكون المرئي، حتى لو كان لديه وقت غير محدود للتفكير بين الأسئلة. وهذا يضع فجوة رياضية صارمة حيث ينجح الجهاز الكمومي في المكان الذي يعجز فيه الجهاز الكلاسيكي بشكل مثبت.
وتذهب النتائج إلى أبعد من ذلك؛ فقد أظهر الباحثون أنه من خلال تحسين الطريقة الكمومية للتعامل مع أنماط الخطأ الأكثر تعقيداً، استطاعوا رفع معدل النجاح بشكل أكبر، ليصل إلى درجات تقارب 96 بالمائة في الحالات العشوائية النموذجية، وفي بعض الحالات، العثور على حل مثالي يستوفي كل قاعدة واحدة. يأتي هذا التحسن من استخدام استراتيجية فك ترميز أكثر قوة تأخذ في الاعتبار احتمالات متعددة في آن واحد بدلاً من مجرد التخمين الأفضل الوحيد. وبينما يظل الحد الكلاسيكي ثابتاً عند 65 بالمائة، فإن السقف الكمومي يرتفع بشكل ملحوظ، اعتماداً على المعايير المحددة للغز. وتؤكد الدراسة أن هذه الميزة ليست مجرد مسألة سرعة، بل هي مسألة قدرة؛ فالخوارزمية الكمومية تصل إلى فضاء حلول غير مرئي فعلياً لأي طريقة كلاسيكية تعمل تحت نفس القيود.
لقد حسم هذا العمل تساؤلاً طال أمدُه حول ما إذا كانت الحواسيب الكمومية يمكن أن تقدم ميزة صارمة للتحسين التقريبي، وهو مجال كانت نتائجه السابقة غالباً مشروطة بافتراضات غير مثبتة أو مقتصرة على حالات محددة وغير عشوائية. ومن خلال بناء سيناريو تكون فيه القواعد عشوائية ولكن البنية صريحة، قدم الفريق برهاناً نظيفاً وغير مشروط على التفوق الكمومي. ولا يعتمد هذا النتيجة على كون الحاسوب الكمومي أسرع في كل خطوة، بل على قدرته على التنقل في مشهد من الاحتمالات بطريقة لا يمكن للمنطق الكلاسيكي تكرارها. وبالنسبة لعائلة المشكلات المختبرة، فإن النهج الكمومي ليس فقط أفضل، بل هو الطريقة الوحيدة المعروفة لتجاوز حاجز أداء معين. وهذا يشير إلى أنه بالنسبة لمجموعة واسعة من تحديات التحسين في العالم الحقيقي التي تشترك في هذه الخصائص الهيكلية، قد تتمكن الأجهزة الكمومية قرياً من تقديم حلول لا يمكن الوصول إليها حالياً حتى بواسطة أقوى الحواسيب الفائقة.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.