DOI: https://doi.org/10.1038/s41534-025-01020-1
تاريخ النشر: 2025-05-16
المؤلف: Seongmin Kim وآخرون
الموضوع الرئيسي: خوارزميات وهندسة الحوسبة الكمومية
نظرة عامة
في هذا القسم، يناقش المؤلفون التقدم في تكنولوجيا التبريد الكمي (QA) وآثارها على حل مشاكل تحسين التوليف. على الرغم من القيود السابقة في عدد الكيوبتات والاتصال التي أعاقت أداء QA مقارنة بالطرق الكلاسيكية، فقد قدمت التطورات الأخيرة أجهزة تبريد كمي تحتوي على أكثر من 5000 كيوبت وتحسينات في الاتصال. تشير هذه التحسينات، إلى جانب الهياكل الهجينة، إلى إمكانية تحقيق ميزة كمية.
يقوم المؤلفون بتقييم أداء حل كمي متطور مقابل الحلول الكلاسيكية من خلال معالجة أكثر من 50 حالة من مشاكل التحسين التي تتميز بمصفوفات هاملتونية كبيرة وكثيفة. تكشف النتائج أن الحل الكمي يحقق دقة أعلى تبلغ حوالي 0.013% وسرعة ملحوظة تصل إلى حوالي 6561 مرة مقارنة بأفضل حل كلاسيكي. تؤكد هذه الدراسة على فعالية QA، خاصة في التكوينات الهجينة، في تقديم دقة متفوقة وأوقات حل مشاكل مخفضة بشكل كبير لتحديات تحسين العالم الحقيقي على نطاق واسع.
طرق
في هذا القسم، يحدد المؤلفون مشكلة تحسين ثنائية غير مقيدة تربيعية (QUBO) ويحددون طرقًا مختلفة لحلها، خاصة في سياق التبريد الكمي (QA) وتقنيات التحسين الكلاسيكية. يتم تمثيل QUBO بواسطة مصفوفة \( Q \) تتكون من معاملات خطية للمتغيرات الفردية ومعاملات تربيعية للتفاعلات بين أزواج المتغيرات. الهدف هو العثور على متجه ثنائي \( x \) يقلل من الناتج القياسي \( y \)، كما هو معبر عنه في المعادلات \( y = \sum_{i=1}^{n} \sum_{j=i}^{n} Q_{i,j} x_i x_j \) و \( x^* = \arg\min_x y \). يمكن تعلم المعاملات من البيانات باستخدام نماذج التعلم الآلي، مما يسمح بتمثيل مشاكل التحسين المعقدة كـ QUBOs.
يقوم المؤلفون بتقييم سبع طرق لحل مشاكل QUBO: التبريد الكمي (QA)، التبريد الكمي الهجين (HQA)، البرمجة الصحيحة (IP)، التبريد المحاكي (SA)، الانحدار الأكثر حدة (SD)، البحث المحظور (TS)، والتبريد المتوازي مع تحركات الكتل المتساوية الطاقة (PT-ICM). يتم وصف كل طريقة بإيجاز، مع تسليط الضوء على مبادئ تشغيلها وإعدادات المعلمات الفائقة. على سبيل المثال، يستخدم QA جهاز تبريد كمي للتطور من هاملتوني أولي إلى هاملتوني المشكلة، بينما يستخدم SA نهجًا احتماليًا لتقريب الأمثل العالمي. يذكر المؤلفون أيضًا استخدام مجموعة أدوات تطوير البرمجيات D-Wave Ocean لتنفيذ هذه الحلول وحزمة QBSolv لتفكيك مصفوفات QUBO الأكبر إلى مشاكل فرعية أصغر يمكن إدارتها. تهدف هذه المنهجية الشاملة إلى معالجة مجموعة من تحديات تحسين التوليف بشكل فعال.
نتائج
تسلط نتائج هذه الدراسة المرجعية على مشاكل تحسين التوليف الضوء على التحديات التي تطرحها مصفوفات تحسين ثنائية غير مقيدة تربيعية (QUBO) الكبيرة والكثيفة، خاصة في التطبيقات الواقعية مثل تصميم المواد. تؤدي الحلول الكلاسيكية، بما في ذلك البرمجة الصحيحة (IP)، والتبريد المحاكي (SA)، والانحدار الأكثر حدة (SD)، والبحث المحظور (TS)، بشكل كافٍ للمشاكل الأصغر ولكنها تكافح مع الدقة والكفاءة مع زيادة حجم المشكلة (≥ 1000 متغير). من الجدير بالذكر أنه بينما يعزز الجمع بين التبريد المتوازي وتحركات الكتل المتساوية الطاقة (PT-ICM) استكشاف فضاء الحل، فإن فعاليته تتناقص للمشاكل الأكثر كثافة. إن دمج استراتيجيات تفكيك QUBO مع الحلول الكلاسيكية (مثل SA-QBSolv) يحسن الأداء ولكنه لا يزال غير كافٍ للمشاكل الكبيرة جدًا، خاصة فيما يتعلق بالوقت الحاسوبي.
في المقابل، تظهر الحلول الكمية، وخاصة الخوارزميات الكمية الهجينة (HQA)، أداءً متفوقًا في حل مشاكل QUBO على نطاق واسع. تكشف الدراسة أن الأساليب الكمية تحقق باستمرار حلول عالية الجودة عبر أحجام مشاكل متنوعة، حيث تتفوق HQA بشكل كبير على الطرق الكلاسيكية من حيث الدقة والكفاءة الحاسوبية. على سبيل المثال، عند حجم مشكلة يبلغ 10,000 متغير، تحقق HQA وقت حل قدره 0.0855 ثانية، مقارنة بـ 561 ثانية لـ SA-QBSolv. تشير النتائج إلى أن الاستفادة من الموارد الكمية، خاصة في التكوينات الهجينة، توفر ميزة حاسوبية على الأساليب الكلاسيكية، مع توقعات لمزيد من التحسينات مع تطور الأجهزة الكمية.
مناقشة
في هذه المناقشة، يقيم البحث أداء أجهزة وبرامج التبريد الكمي (QA) مقابل الحلول الكلاسيكية لتحسين مشاكل QUBO الكبيرة، خاصة تلك التي تحتوي على ما يصل إلى 10,000 متغير وتفاعلات متصلة بالكامل. تكافح الحلول الكلاسيكية، على الرغم من تحسينها من خلال طرق مثل تفكيك QUBO (مثل QBSolv)، مع الدقة والكفاءة مع زيادة أحجام المشاكل، مما يبرز قيودها في معالجة السيناريوهات المعقدة في العالم الحقيقي. في المقابل، تظهر أجهزة التبريد الكمي الهجينة (HQA) أداءً متفوقًا، حيث تحقق دقة أعلى تبلغ حوالي 0.013% وتسريعًا ملحوظًا بمقدار 6561 مرة في وقت الحل لمشاكل QUBO الكبيرة. على الرغم من القيود الحالية للأجهزة التي تحد من QA النقي وQA مع طرق التفكيك، يتوقع المؤلفون أن التقدم في التكنولوجيا الكمية سيمكن QA من تحقيق “الميزة الكمية” الحقيقية في المستقبل.
تركز دراسة المرجعية على تحسين المواد، وتحديدًا تصميم الطبقات المتعددة المستوية (PMLs) للتطبيقات البصرية، والتي تمثل مشكلة واقعية نموذجية. يتم نمذجة تكوينات هذه الطبقات المتعددة كمتجهات ثنائية، مع حساب خصائصها البصرية باستخدام طريقة المصفوفة الانتقالية (TMM). تصيغ الدراسة مصفوفات QUBO من هذه التكوينات، مما يعكس الطبيعة الكثيفة لمشاكل التحسين في العالم الحقيقي. بالإضافة إلى ذلك، يستكشف البحث بشكل منهجي قابلية التوسع من خلال تغيير أحجام المشاكل وتوزيعات العناصر، مع مقاييس الأداء التي تشمل الدقة النسبية والوقت الحاسوبي. يسمح مقياس الدقة النسبية بتقييم مقارن لأداء الحلول، بينما يتم قياس الوقت الحاسوبي لتقييم كفاءة كل من الحلول الكلاسيكية والكمية، مما يبرز الطبيعة الصعبة NP لمشاكل QUBO المعالجة.
DOI: https://doi.org/10.1038/s41534-025-01020-1
Publication Date: 2025-05-16
Author(s): Seongmin Kim et al.
Primary Topic: Quantum Computing Algorithms and Architecture
Overview
In this section, the authors discuss the advancements in quantum annealing (QA) technology and its implications for solving combinatorial optimization problems. Despite previous limitations in qubit count and connectivity that hindered QA’s performance compared to classical methods, recent developments have introduced quantum annealers with over 5000 qubits and improved connectivity. These enhancements, along with hybrid architectures, suggest a potential realization of quantum advantage.
The authors benchmark the performance of a state-of-the-art quantum solver against classical solvers by addressing over 50 optimization problem instances characterized by large and dense Hamiltonian matrices. The findings reveal that the quantum solver achieves a higher accuracy of approximately 0.013% and a remarkable speedup of about 6561 times compared to the best classical solver. This study underscores the effectiveness of QA, particularly in hybrid configurations, in delivering superior accuracy and significantly reduced problem-solving times for large-scale real-world optimization challenges.
Methods
In this section, the authors define the Quadratic Unconstrained Binary Optimization (QUBO) problem and outline various methods for solving it, particularly in the context of quantum annealing (QA) and classical optimization techniques. A QUBO is represented by a matrix \( Q \) that consists of linear coefficients for individual variables and quadratic coefficients for interactions between pairs of variables. The goal is to find a binary vector \( x \) that minimizes the scalar output \( y \), as expressed in the equations \( y = \sum_{i=1}^{n} \sum_{j=i}^{n} Q_{i,j} x_i x_j \) and \( x^* = \arg\min_x y \). The coefficients can be learned from data using machine learning models, allowing the representation of complex optimization problems as QUBOs.
The authors benchmark seven methods for solving QUBO problems: Quantum Annealing (QA), Hybrid Quantum Annealing (HQA), Integer Programming (IP), Simulated Annealing (SA), Steepest Descent (SD), Tabu Search (TS), and Parallel Tempering with Isoenergetic Cluster Moves (PT-ICM). Each method is briefly described, highlighting their operational principles and hyperparameter settings. For instance, QA utilizes a quantum annealer to evolve from an initial Hamiltonian to a problem Hamiltonian, while SA employs a probabilistic approach to approximate global optima. The authors also mention the use of the D-Wave Ocean software development kit for implementing these solvers and the QBSolv package for decomposing larger QUBO matrices into smaller, manageable subproblems. This comprehensive methodology aims to effectively tackle a range of combinatorial optimization challenges.
Results
The results of this benchmarking study on combinatorial optimization problems highlight the challenges posed by large and dense Quadratic Unconstrained Binary Optimization (QUBO) matrices, particularly in real-world applications such as materials design. Classical solvers, including integer programming (IP), simulated annealing (SA), steepest descent (SD), and tabu search (TS), perform adequately for smaller problems but struggle with accuracy and efficiency as problem size increases (≥ 1000 variables). Notably, while the combination of parallel tempering and isoenergetic cluster moves (PT-ICM) enhances exploration of the solution space, its effectiveness diminishes for denser problems. The integration of QUBO decomposition strategies with classical solvers (e.g., SA-QBSolv) improves performance but remains insufficient for very large problems, particularly regarding computational time.
In contrast, quantum solvers, especially hybrid quantum algorithms (HQA), demonstrate superior performance in solving large-scale QUBO problems. The study reveals that quantum approaches consistently yield high-quality solutions across varying problem sizes, with HQA significantly outperforming classical methods in both accuracy and computational efficiency. For instance, at a problem size of 10,000 variables, HQA achieves a solving time of 0.0855 seconds, compared to 561 seconds for SA-QBSolv. The findings suggest that leveraging quantum resources, particularly in hybrid configurations, offers a computational advantage over classical approaches, with expectations for further improvements as quantum hardware evolves.
Discussion
In this discussion, the research evaluates the performance of quantum annealing (QA) hardware and software against classical optimization solvers for large Quadratic Unconstrained Binary Optimization (QUBO) problems, particularly those with up to 10,000 variables and fully connected interactions. Classical solvers, while improved through methods like QUBO decomposition (e.g., QBSolv), struggle with accuracy and efficiency as problem sizes increase, highlighting their limitations in addressing complex real-world scenarios. In contrast, hybrid quantum annealers (HQA) demonstrate superior performance, achieving approximately 0.013% higher accuracy and a remarkable 6561-fold acceleration in solution time for large QUBO problems. Despite current hardware constraints limiting pure QA and QA with decomposition methods, the authors anticipate advancements in quantum technology will enable QA to achieve true “Quantum Advantage” in the future.
The benchmarking study focuses on material optimization, specifically the design of planar multilayers (PMLs) for optical applications, which serve as a representative real-world problem. The configurations of these multilayers are modeled as binary vectors, with their optical characteristics calculated using the transfer matrix method (TMM). The study formulates QUBO matrices from these configurations, reflecting the dense nature of real-world optimization problems. Additionally, the research systematically explores scalability by varying problem sizes and element distributions, with performance metrics including relative accuracy and computational time. The relative accuracy metric allows for a comparative assessment of solver performance, while computational time is measured to evaluate the efficiency of both classical and quantum solvers, underscoring the NP-hard nature of the QUBO problems addressed.