DOI: https://doi.org/10.1038/s43588-026-00991-1
PMID: https://pubmed.ncbi.nlm.nih.gov/42343114
تاريخ النشر: 2026-06-23
المؤلف: Thorsten Koch وآخرون
الموضوع الرئيسي: خوارزميات وهندسة الحوسبة الكمومية
نظرة عامة
يتناول هذا القسم التقدمات الأخيرة في تقييم خوارزميات الكم الاستدلالية، لا سيما في مجال تحسين التوليفات، حيث تعتبر التحليلات التجريبية ضرورية لتقييم التقدم نحو تحقيق ميزة الكم. يقترح المؤلفون إطار عمل منهجي للتقييم يتضمن عشرة فئات من المشكلات المستقلة عن النموذج، والتي تم تصميمها لتكون تحديًا للخوارزميات الكلاسيكية. تختلف فئات المشكلات هذه في التعقيد، حيث تصبح صعبة مع أقل من 100 إلى حد أقصى 100,000 متغير قرار. يرافق العمل مستودع مفتوح المصدر، يوفر سجلات تتبع لحالات محددة وحلول.
تسلط الورقة الضوء على أهمية التحسين في مجالات مختلفة مثل تصميم التجارب، طي البروتينات، اللوجستيات، والمالية، حيث يمكن أن تعزز الخوارزميات المحسنة الأداء وكفاءة التكلفة. تصنف خوارزميات التحسين إلى ثلاثة أنواع: دقيقة مثبتة، تقريبية مثبتة، وخوارزميات استدلالية. يتم تصنيف العديد من مشاكل التحسين ذات الصلة على أنها NP-hard، مما يشير إلى أن الموارد اللازمة لإيجاد الحلول المثلى تزداد بشكل أسي مع حجم المشكلة. يشير المؤلفون إلى أنه بينما من غير المحتمل أن توجد خوارزميات فعالة دقيقة مثبتة لمشاكل NP-hard، تواجه الخوارزميات التقريبية المثبتة قيودًا بسبب حدود عدم التقريب المعروفة، مما يحد من أدائها.
الطرق
في قسم الطرق، يحدد المؤلفون أنواع المشكلات التي تم تناولها في بحثهم، والأساليب النمذجة المستخدمة، ومقاييس الأداء المستخدمة للتقييم. يشيرون إلى القراء إلى قسم “النتائج” لمناقشة شاملة حول فئة المجموعة المستقلة القصوى، بينما يتم تفصيل الحالات المحددة والنتائج الأساسية المستمدة من حلول التحسين الكلاسيكية في المعلومات التكميلية تحت “فئات المشكلات”. يوضح المؤلفون أن نتائجهم الأساسية ليست بالضرورة الحلول المثلى القابلة للتحقيق بواسطة الحواسيب الكلاسيكية ولكنها تعمل كمعيار لإظهار قدرات الحلول العامة دون جهود تحسين واسعة.
بالإضافة إلى ذلك، لم تخضع صيغ البرمجة المختلطة الصحيحة (MIP) وتحسين ثنائي غير مقيد تربيعي (QUBO) المقدمة لعمليات تحسين صارمة وتهدف بشكل أساسي كأمثلة توضيحية. تم تنفيذ هذه الصيغ على مجموعة حوسبة مع معلمات افتراضية في الغالب. جميع الحالات والنماذج والحلول المستخدمة في الدراسة متاحة في المستودع المرتبط، مما يضمن الشفافية وقابلية إعادة إنتاج نتائج البحث.
النتائج
تحدد قسم النتائج في هذه الورقة البحثية عشرة فئات من المشكلات التي تقدم تحديات كبيرة لأساليب التحسين الحديثة، حتى على نطاقات صغيرة. هذه الفئات من المشكلات ذات صلة خاصة بالتطبيقات العملية، حيث تعالج فجوة في الأدبيات حيث نادرًا ما يتم نشر المشكلات الصناعية غير المحلولة، وغالبًا ما يتم تبسيط المشكلات القابلة للحل إلى حد فقدان تعقيدها. يؤكد المؤلفون على الحاجة إلى إطار تقييم يتضمن مشكلات تحسين صعبة حقًا لتسهيل المقارنات العادلة بين خوارزميات الكم والكلاسيكية.
تشمل معايير اختيار هذه الفئات من المشكلات متطلبات نمذجة المتغيرات الصحيحة، ويفضل أن تكون ثنائية، لضمان سهولة التحقق من القابلية والتوافق مع خوارزميات تحسين الكم. بالإضافة إلى ذلك، تتميز الحالات المختارة بصعوبتها بالنسبة للأساليب الكلاسيكية، لا سيما بسبب التعقيد الأولي، مع ضمان أن جميع الحالات لديها حلول قابلة للحل. توفر الورقة معلومات مفصلة حول حالات المشكلات، بما في ذلك صيغها كنماذج برمجة مختلطة صحيحة (MIP) وتحسين ثنائي غير مقيد تربيعي (QUBO)، مع تسليط الضوء على مقاييس رئيسية مثل عدد المتغيرات، وكثافة المشكلة، ونطاقات المعاملات. من الجدير بالذكر أن فئات مشكلات تقسيم السوق، LABS، والمجموعة المستقلة تم تحديدها على أنها مناسبة بشكل خاص لأساليب الكم بسبب حالات التحدي الخاصة بها في الأحجام الصغيرة. تتوفر مزيد من التفاصيل والمعايير لهذه الفئات من المشكلات في المواد التكميلية.
المناقشة
في هذا القسم، يناقش المؤلفون التحديات والتطبيقات العملية لمشكلات تحسين التوليفات، مع التركيز بشكل خاص على مشكلة المجموعة المستقلة القصوى (MIS) وأهميتها في تقييم خوارزميات الكم. يبرزون تعقيد تعريف حالات المشكلات التمثيلية بسبب التباينات الواسعة في التطبيقات الواقعية، مثل تحسين المحافظ وتوجيه المركبات، مما يعقد تقييم خوارزميات الكم. يهدف المؤلفون إلى معالجة هذه الفجوة من خلال تقديم مجموعة من حالات المشكلات التي يمكن استخدامها لتقييم أداء طرق تحسين الكم، مشيرين إلى أن حالات مشكلة توجيه المركبات الحالية يمكن حلها بشكل مثالي باستخدام الأساليب الكلاسيكية، وهو قيد يعتزمون تصحيحه في الأعمال المستقبلية.
تُفصَّل مشكلة المجموعة المستقلة القصوى، وهي مشكلة NP-hard معروفة، حيث تتعلق بنظرية الرسوم البيانية وتحسين التوليفات. يصف المؤلفون صياغتها الرياضية والتحديات المرتبطة بحلها، لا سيما بالنسبة للرسوم البيانية الأكبر. كما يناقشون إمكانية أن توفر خوارزميات الكم تسريعًا في حل مثل هذه المشكلات، على الرغم من أن العروض العملية لميزة الكم لا تزال بعيدة المنال. يبرز القسم أهمية اختيار فئات المشكلات التي تكون صعبة بالنسبة للأساليب الكلاسيكية ومناسبة للاستكشاف الكم، بينما يؤسس أيضًا مستودعًا حيًا للمساهمات والتحديثات المستمرة في هذا المجال. يدعو المؤلفون الباحثين للتفاعل مع حالات المشكلات المقدمة ومشاركة نتائجهم، مؤكدين على الحاجة إلى تحسين مستمر في كل من منهجيات تحسين الكم والكلاسيكية.
DOI: https://doi.org/10.1038/s43588-026-00991-1
PMID: https://pubmed.ncbi.nlm.nih.gov/42343114
Publication Date: 2026-06-23
Author(s): Thorsten Koch et al.
Primary Topic: Quantum Computing Algorithms and Architecture
Overview
This section discusses recent advancements in benchmarking heuristic quantum algorithms, particularly in the realm of combinatorial optimization, where empirical analysis is crucial for assessing progress towards achieving quantum advantage. The authors propose a systematic benchmarking framework that includes ten model-independent problem classes, which are designed to be challenging for classical algorithms. These problem classes vary in complexity, becoming difficult with fewer than 100 to a maximum of 100,000 decision variables. An open-source repository accompanies the work, providing track records of specific instances and solutions.
The paper highlights the importance of optimization in various fields such as experiment design, protein folding, logistics, and finance, where improved algorithms can enhance performance and cost efficiency. It categorizes optimization algorithms into three types: provably exact, provably approximate, and heuristic algorithms. Many relevant optimization problems are classified as NP-hard, indicating that the resources needed to find optimal solutions increase exponentially with problem size. The authors note that while provably exact efficient algorithms are unlikely to exist for NP-hard problems, provably approximate algorithms face limitations due to known inapproximability bounds, which restrict their performance.
Methods
In the Methods section, the authors outline the problem types addressed in their research, the modeling approaches employed, and the performance metrics utilized for evaluation. They refer readers to the ‘Results’ section for a comprehensive discussion on the maximum independent set class, while specific instances and baseline results derived from classical optimization solvers are detailed in the Supplementary Information under “Problem classes.” The authors clarify that their baseline results are not necessarily the optimal solutions achievable by classical computers but serve as a benchmark to demonstrate the capabilities of general solvers without extensive optimization efforts.
Additionally, the Mixed Integer Programming (MIP) and Quadratic Unconstrained Binary Optimization (QUBO) formulations presented were not subjected to rigorous optimization and are intended primarily as illustrative examples. These formulations were executed on a compute cluster with predominantly default parameters. All instances, models, and solutions utilized in the study are made available in the associated repository, ensuring transparency and reproducibility of the research findings.
Results
The results section of this research paper identifies ten problem classes that present significant challenges for state-of-the-art optimization methods, even at small scales. These problem classes are particularly relevant to practical applications, addressing a gap in the literature where unsolved industrial problems are seldom published, and feasible problems are often simplified to the point of losing their complexity. The authors emphasize the need for a benchmarking framework that includes genuinely difficult optimization problems to facilitate fair comparisons between quantum and classical algorithms.
The selection criteria for these problem classes include the requirement for integer variable modeling, preferably binary, to ensure ease of feasibility checks and compatibility with quantum optimization algorithms. Additionally, the instances chosen are characterized by their difficulty for classical methods, particularly due to primal complexity, while ensuring that all instances have feasible solutions. The paper provides detailed information on the problem instances, including their formulations as Mixed Integer Programming (MIP) and Quadratic Unconstrained Binary Optimization (QUBO) models, highlighting key metrics such as the number of variables, problem density, and coefficient ranges. Notably, the Market Split, LABS, and Independent Set problem classes are identified as particularly suitable for quantum approaches due to their challenging instances at smaller sizes. Further details and benchmarks for these problem classes are available in the supplementary materials.
Discussion
In this section, the authors discuss the challenges and practical applications of combinatorial optimization problems, particularly focusing on the maximum independent set (MIS) problem and its relevance in benchmarking quantum algorithms. They highlight the complexity of defining representative problem instances due to the vast variations in real-world applications, such as portfolio optimization and vehicle routing, which complicate the benchmarking of quantum algorithms. The authors aim to address this gap by providing a selection of problem instances that can be used to evaluate the performance of quantum optimization methods, noting that existing vehicle routing problem instances can be optimally solved with classical methods, a limitation they intend to rectify in future work.
The maximum independent set problem, a well-known NP-hard problem, is detailed as it relates to graph theory and combinatorial optimization. The authors describe its mathematical formulation and the challenges associated with solving it, particularly for larger graphs. They also discuss the potential for quantum algorithms to provide speed-ups in solving such problems, although practical demonstrations of quantum advantage remain elusive. The section emphasizes the importance of selecting problem classes that are difficult for classical methods and suitable for quantum exploration, while also establishing a living repository for ongoing contributions and updates in the field. The authors invite researchers to engage with the provided problem instances and share their findings, underscoring the need for continuous improvement in both quantum and classical optimization methodologies.