A quantum central path algorithm for linear optimization
تقترح الورقة البحثية خوارزمية كمومية جديدة تحل مسائل الأمثلية الخطية عبر محاكاة المسار المركزي بواسطة معادلات التكامل غير الخطي، محققةً أمثلية بمقدار ε مع تحسين تعقيدات الاستعلام والبوابة اعتماداً على حجم المسألة وندرتها.
التحسين هو الفن الرياضي لإيجاد أفضل حل ممكن لمشكلة ما، سواء كان ذلك يعني توجيه شاحنة توصيل عبر المسار الأكثر كفاءة في حركة المرور، أو موازنة محفظة مالية، أو تصميم جسر مستقر. لعقود من الزمن، كانت الأساليب الأكثر قوة لحل هذه المشكلات هي طرق النقطة الداخلية. لا تقفز هذه الخوارزميات مباشرة إلى الإجابة؛ بل تتبع بدلاً من ذلك مساراً متعرجاً وغير مرئي يُعرف بالمسار المركزي. تخيل متنزهاً يتنقل في سلسلة جبال: بدلاً من تسلق كل قمة أو الهبوط في كل وادٍ، يلتزم المتنزه بقمة جبلية محددة تقوده مباشرة إلى أدنى نقطة. في عالم التحسين الخطي، هذا المسار هو منحنى سلس تحدده مجموعة من المعادلات التي توازن قيود المشكلة. تتبع الحواسيب الكلاسيكية هذا المسار عبر اتخاذ خطوات صغيرة ومحسوبة، وحل معادلة خطية معقدة عند كل منعطف لتحديد الخطوة التالية. ورغم فعاليتها، إلا أن هذا النهج القائم على الخطوة تلو الأخرى يمكن أن يصبح بطيئاً للغاية ويستهلك الكثير من الموارد مع زيادة حجم المشكلات، مما يتطلب من الحاسوب إجراء ملايين الحسابات لمجرد الاقتراب من الحل.
لقد اقترح فريق من الباحثين الآن طريقة مختلفة جذرياً للسفر عبر هذا المسار، وهي طريقة تتجاوز الحسابات الخطوة بخطوة تماماً باستخدام القوانين الفريدة لميكانيكا الكم. في دراسة جديدة، وصفوا خوارزمية كمومية تعامل المسار المركزي ليس كسلسلة من الخطوات المنفصلة التي يجب حلها، بل كمشهد فيزيائي يمكن عبوره في حركة واحدة مستمرة. وبدلاً من حل المعادلات لإيجاد النقطة التالية على المسار، تحاكي الخوارزمية سلوك جسيم كمومي يتحرك عبر مجال طاقة مصمم خصيصاً. وقد تم بناء هذا المجال بحيث تستقر حالته ذات الطاقة الأدنى، والمعروفة باسم الحالة الأرضية، تماماً حيث يقع الحل الأمثل للمشكلة. ومن خلال إعداد نظام كمومي في هذه الحالة وتوجيهه على طول المسار، أظهر الباحثون أن النظام يمكنه الوصول إلى الحل دون الحاجة إلى التكرار والعودة ذهاباً وإياباً الذي يبطئ الحواسيب الكلاسيكية.
يعتمد جوهر هذه الطريقة الجديدة، التي أطلق عليها المؤلفون اسم "طريقة المسار المركزي الكمومي"، على مفهوم يسمى محاكاة الهاميلتونيان. في الفيزياء الكمومية، الهاميلتونيان هو مؤثر يمثل الطاقة الإجمالية للنظام، حيث يجمع بين حركته وموقعه داخل مجال جهد. صمم الباحثون "هاميلتونيان" محدداً حيث يكون جزء "طاقة الوضع" في المعادلة مشكلاً على هيئة المسار المركزي نفسه. عندما يكون النظام الكمومي في أدنى حالات طاقته، يتركز توزيع احتماليته فوق الحل الأمثل مباشرة. ومع ذلك، فإن التحدي يكمكم في أن شكل مشهد الطاقة هذا يتغير مع اقتراب الخوارزمية من الحل. وللتغلب على ذلك، طور الفريق جدولاً زمنياً من مرحلتين؛ أولاً، يحركون النظام على طول المسار مع إبقاء مشهد الطاقة عريضاً نسبياً، مما يسمح للحالة الكمومية بالتدفق بسلاسة من نقطة البداية إلى محيط الحل. وفي المرحلة الثانية، يقومون بتضييق مشهد الطاقة، وضغط الحالة الكمومية في قمة حادة ودقيقة تقابل الإجابة الصحيحة.
يوفر هذا النهج ميزة كبيرة مقارنة بالمحاولات السابقة لاستخدام الحواسيب الكمومية في التحسين. حاولت الخوارزميات الكمومية السابقة تسريع الخطوات الفردية للطريقة الكلاسيكية، حيث طلبت من الحاسوب الكمومي فعلياً حل المعادلات الخطية بشكل أسرع. ومع ذلك، كانت تلك الطرق لا تزال تتطلب من الحاسوب اتخاذ نفس عدد الخطوات التي يتخذها الحاسوب الكلاسيكي، وغالباً ما اعتمدت على نظام ذاكرة نظري يسمى ذاكرة الوصول العشوائي الكمومية، وهو نظام لا يوجد له شكل عملي حتى الآن. تتجنب الطريقة الجديدة هذا الاعتماد تماماً؛ فهي لا تحاول تسريع خطوة واحدة، بل تستبدل العملية التكرارية بأكملها بتطور كمومي واحد. وقد أثبت الباحثون أن هذه الخوارزمية يمكنها إيجاد حل لمشكلة تحسين خطي بمستوى معين من الدقة باستخدام عدد من العمليات يتناسب بكفاءة مع حجم المشكلة. والأهم من ذلك، أن هذه الكفاءة تظل قائمة حتى بدون استخدام ذاكرة الوصول العشوائي الكمومية، مما يجعل النهج قابلاً للتطبيق المحتمل على الأجهزة المستقبلية التي تعتمد على البوابات الكمومية القياسية.
للتحقق من أن إطارهم النظري يعمل في الممارسة العملية، أجرى الباحثون عرضاً عددياً على جهاز كمبيوتر محمول عادي. لقد أخذوا مشكلة تحسين بسيطة وصغيرة واختزلوها من معادلات كمومية عالية الأبعاد إلى نسخة ثنائية الأبعاد يمكن تصورها. وأظهرت النتائج أن كثافة الاحتمالية للحالة الكمومية، والتي بدت مثل سحابة من الضباب، بدأت عريضة ومركزة على النقطة الأولية. ومع تقدم المحاكاة وتعديل المعايير، ضاقت السحابة وتحركت، متبعة المسار المنحني نحو الحل الأمثل. وبنهاية المحاكاة، انكمشت السحابة لتصبح بقعة ساطعة وضيقة في المكان الذي توجد فيه الإجابة الصحيحة تماماً. وقد أثبت هذا التأكيد البصري أن الحالة الكمومية يمكنها بالفعل تتبع المسار المركزي والتركيز على الحل كما تنبأت النظرية.
تمتد آثار هذا العمل إلى ما هو أبعد من مجرد حل المعادلات الخطية بشكل أسرع. إذ تؤسس الدراسة رابطاً جديداً بين النظرية الرياضية لطرق النقطة الداخلية والمحاكاة الفيزيائية للأنظمة الكمومية. وهي تشير إلى أن مشكلات التحسين يمكن النظر إليها كنظم ديناميكية تتطور بمرور الوقت، بدلاً من كونها ألغازاً ثابتة تُحل بالتكرار. وبينما لا تزال هذه الخوارزمية مقترحاً نظرياً ولم يتم تشغيلها بعد على حاسوب كمومي واسع النطاق، فإن البراهين الرياضية والمحاكاة الناجحة على نطاق صغير توفر أساساً قوياً. ويشير الباحثون إلى أن إطار عملهم يمكن تعديله ليشمل أنواعاً أكثر تعقيدداً من التحسين، مثل تلك التي تتضمن البرمجة شبه المحددة أو قيود المخروط من الدرجة الثانية. ومن خلال إظهار أن الحاسوب الكمومي يمكنه عبور المسار المركزي في حركة واحدة متماسكة، يفتح هذا العمل مساراً جديداً لحل بعض أصعب المشكلات الحسابية في عصرنا، مبتعداً عن قيود التكرار الكلاسيكي نحو طريقة كمومية أكثر طبيعية لإيجاد أفضل إجابة.
ملخص تقني: خوارزمية المسار المركزي الكمي للتحسين الخطي
بيان المشكلة تتناول الورقة مشكلة حل مسائل التحسين الخطي (LO) من الشكل minc⊤x بشرط Ax≥b,x≥0 ومسألتها المزدوجة المرتبطة بها. وبينما تُعد طرق النقاط الداخلية الكلاسيكية (IPMs) هي الأفضل حالياً لحل هذه المسائل، إلا أنها تعتمد على خطوات نيوتن تكرارية تتطلب حل أنظمة خطية كبيرة (نظام نيوتن الخطي) في كل تكرار. وتحاول طرق النقاط الداخلية الكمية (QIPMs) الحالية تسريع هذه العملية باستخدام خوارزميات الأنظمة الخطية الكمية (QLSAs) لحل هذه الأنظمة الخطية. ومع ذلك، تعاني طرق QIPMs الحالية من عيبين رئيسيين: (1) تتطلب عادةً نموذج ذاكرة الوصول العشوائي الكمي (QRAM)، وهو ما يُعتبر غير عملي للأجهزة القريبة من الواقع الحالي؛ و(2) تظل تكرارية، حيث ترث تعقيد التكرار O(nlog(1/ε)) الخاص بطرق IPM الكلاسيكية، وتعتمد على التصوير المقطعي للحالة الكمية (quantum state tomography) المكلف لاستخراج الحلول الكلاسيكية.
المنهجية يقترح المؤلفون نهجاً جديداً يسمى طريقة المسار المركزي الكمي (QCPM). وبخلاف طرق QIPMs، التي تقوم بـ "تكميم" (quantize) خطوات خوارزمية كلاسيكية، تقوم QCPM بتكميم ديناميكيات المسار المركزي نفسه. تسير المنهجية وفق الخطوات التالية:
صياغة الهاملتوني (Hamiltonian Formulation): يقوم المؤلفون ببناء عائلة من مؤثرات الهاملتوني المعتمدة على الزمن، H(μ,h)، المعرفة فوق الفضاء المتعامد الموجب، حيث يتكون الهاملتوني من مؤثر شرودنجر يتألف من حد طاقة حركية وحد طاقة وضع: H(μ,h)=−2h2∇2+Φμ(z) هنا، μ هو بارامتر المسار المركزي (مرتبط بفجوة الازدواجية)، و h يعمل كبارامتر قياس مشابه لثابت بلانك. دالة طاقة الوضع Φμ(z) مشتقة من دالة حاجز ذاتية التوافق (تحديداً لوغاريتم مستمر تربيعياً)، وقد صُممت بحيث تكون نقطة الحد الأدنى العالمي لها مطابقة تماماً لمركز μ على المسار المركزي لمسألة التحسين الخطي.
ترميز الحالة الأرضية (Ground State Encoding): الجوهر النظري هو أن الحالة الأرضية (المتجه الذاتي ذو أدنى قيمة ذاتية) لـ H(μ,h) ترمز لتوزيع احتمالي متمركز حول المسار المركزي. ومع اقتراب μ من الصفر، يتركز هذا التوزيع حول الحل الأمثل. يتحكم البارامتر h في تباين هذا التوزيع؛ حيث يؤدي تقليل h إلى "ضغط" الحزمة الموجية حول الحل.
عبور المسار الذاتي (Eigenpath Traversal): بدلاً من تكرار خطوات نيوتن، تعبر الخوارزمية مسار الحالة الأرضية للهاملتوني. يستخدم المؤلفون جدولاً زمنياً ذا مرحلتين للبارامترات (μ,h):
المرحلة 1 (النقل - Transport): يتناقص μ من 1 إلى ε بينما يكون h=μ. هذا يحرك المركز لـ الحالة الأرضية على طول المسار المركزي.
المرحلة 2 (الضغط - Squeezing): يتم تثبيت μ عند ε، ويتم تقليل h إلى قيمة مستهدفة h∗ لتضييق التوزيع حول الحل الأمثل عند ε. تم بناء هذا الجدول لضمان أن الحالات الأرضية المتعاقبة تمتلك تداخلاً كبيراً (>1/3)، مما يستوفي شروط خوارزميات عبور المسار الذاتي الفعالة (تحديداً طريقة Boixo وKnill وSomma).
التنفيذ (Implementation): تقوم الخوارزمية بإعداد الحالة الأرضية الأولية (المقابلة لـ μ=1) ثم تحاكي ديناميكيات شرودنجر لعبور المسار. وهي تستخدم التقطيع المكاني (spatial discretization) لتعيين المؤثر ذي الأبعاد اللانهائية إلى مصفوفة ذات أبعاد محدودة مناسبة للحواسيب الكمية القائمة على البوابات (gate-based). والأهم من ذلك، أن الخوارزمية لا تتطلب QRAM؛ فهي تتطلب فقط الوصول إلى وصف ثنائي لبيانات المسألة (A,b,c) عبر "أوراكل" (oracle) لتقييم دالة طاقة الوضع.
المساهمات الرئيسية
نموذج جديد: تقدم الورقة أول خوارزمية كمية تحل مسائل التحسين الخطي عن طريق محاكاة المسار المركزي مباشرة عبر ديناميكيات شرودنجر، بدلاً من تكميم خطوات نيوتن لـ IPMs الكلاسيكية.
الاستقلال عن QRAM: تعمل الخوارزمية في نموذج البوابات القياسي دون الحاجة إلى QRAM، مما يعالج عقبة عملية كبرى في مقترحات QIPM السابقة.
الطبيعة غير التكرارية: يتم الحصول على الحل بطريقة "الطلقة الواحدة" (one-shot) عبر قياس الحالة الكمية النهائية، مما يتجنب الحلقة التكرارية وما يصاحبها من تراكم للأخطاء أو الحاجة إلى تصوير مقطعي متكرر كما في QIPMs.
الضمانات النظرية: يقدم المؤلفون براهين صارمة حول التحدب القوي لدالة الوضع، والفجوة الطيفية للهاملتوني، وتركيز الحالة الأرضية حول المسار المركزي.
النتائج والتعقيد تثبت الورقة أن QCPM يمكنها حل مسألة LO تحتوي على m من القيود و n من المتغيرات لتصل إلى المثالية عند مستوى ε بالتعقيد التالي:
تعقيد الاستعلام (Query Complexity):O~((m+n)3/2ε−1+(m+n)1/2ε−3/2) استعلامات لـ "أوراكل" دالة الوضع.
تعقيد البوابات (Gate Complexity):O~([(m+n)3/2ε−1+(m+n)1/2ε−3/2]⋅nnz(A)) من البوابات الأولية، حيث nnz(A) هو عدد العناصر غير الصفرية في مصفوفة القيود.
يعتمد التعقيد على ندرة المسألة والدقة ε، ولكنه يتجنب بشكل ملحوظ الاعتماد على معامل الشرط (condition number) لبيانات المسألة.
الأهمية والادعاءات يزعم المؤلفون أن هذا العمل يقدم "دليلاً مقنعاً على أن التسريع الكمي الشامل لـ LO قد يكون ممكناً حتى في نموذج الدائرة بدون QRAM". ويؤكدون أن QCPM تقدم نموذجاً جديداً للتحسين الكمي، متميزاً عن نهج "البرنامج الفرعي الكمي" (quantum subroutine) المستخدم في QIPMs السابقة.
وتتسم الورقة بالتواضع فيما يتعلق بمكانتها الحالية، حيث تشير إلى أن:
تحليل الموارد يشير إلى أن الخوارزمية سليمة نظرياً ولكنها قد تتطلب تحسينات كبيرة (خاصة فيما يتعلق بالاعتماد على الخطأ) لتكون عملية على الأجهزة القريبة من الواقع.
تحل الخوارزمية "نموذج التضمين ثنائي الذاتية" (self-dual embedding model) لمسألة LO، وهو نهج نظري قياسي في IPMs الكلاسيكية، بدلاً من حل المسألة الأصلية مباشرة، وإن كان المؤلفون يعتقدون أن معايير الإنهاء المستخدمة في الطرق الكلاسيكية ستنطبق هنا أيضاً.
يوفر الإطار العملي مساراً واعداً وليس له نظير كلاسيكي مباشر معروف، لكن الورقة تضع الأسس للتحليل الصارم بدلاً من ادعاء التفوق العملي الفوري على أفضل الخوارزميات الكلاسية (التي تعمل حالياً بزمن O~((m+n)ω)).
صرح المؤلفون صراحةً أنهم لم يحاولوا بناء نظير كلاسيكي لهذا النظام الديناميكي الكمي، مقرين بأن تصميم نظام كلاسيكي يتتبع الحد الأدنى العالمي لجهد متغير زمنياً سيكون تحدياً كبيراً.
باختيد، تمثل الورقة طفرة نظرية في الربط بين طرق النقاط الداخلية ومحاكة الهاملتوني، مما يفتح مساراً محتملاً للتسريع الكمي للتحسين الخطي يتجاوز قيود QRAM والتصوير المقطعي التكراري.