DOI: https://doi.org/10.1007/s42484-026-00341-4
تاريخ النشر: 2026-02-19
المؤلف: Riccardo Nembrini وآخرون
الموضوع الرئيسي: خوارزميات وهندسة الحوسبة الكمومية
نظرة عامة
تبحث هذه الدراسة في تطبيق التعلم المعزز (RL) للتضمين الثانوي في التلدين الكمي (QA)، مع التركيز بشكل خاص على التحديات المرتبطة بتخطيط مشاكل تحسين ثنائية غير مقيدة تربيعية (QUBO) على الأجهزة الكمومية. يقترح المؤلفون وكيل تحسين السياسة القريب الذي يتعلم إنشاء تضمينات ثانوية من خلال عملية اتخاذ قرارات متسلسلة. تقيم الدراسة أداء الوكيل على كل من الرسوم البيانية للمشاكل المتصلة بالكامل وتلك التي تم إنشاؤها عشوائيًا عبر نوعين من الأجهزة: كيميرا وزيفير. تشير النتائج إلى أن النهج القائم على التعلم المعزز ينتج باستمرار تضمينات ثانوية صالحة، مع تميز خاص في نوع زيفير، الذي يتميز بترابط أعلى للكيوبتات.
في الختام، يعترف المؤلفون بنجاح وكيل التعلم المعزز في تعلم استراتيجيات التضمين الثانوي للرسوم البيانية الأصغر، لكنهم يلاحظون قيوده مع الرسوم البيانية الأكبر، خاصة على نوع كيميرا الأقدم، حيث غالبًا ما تتجاوز متطلبات الكيوبتات تلك الخاصة بالأساليب الحالية مثل minorminer. أدت إدخال تحسينات البيانات، مثل تبديلات الرسوم البيانية العشوائية، إلى تحسين الأداء بشكل كبير للرسوم البيانية التي تم إنشاؤها عشوائيًا. ومع ذلك، واجهت بنية الوكيل صعوبة في الاستفادة الكاملة من الخصائص الهيكلية للرسوم البيانية، مما يشير إلى الحاجة إلى مزيد من الاستكشاف للهياكل البديلة، مثل الشبكات العصبية الرسومية (GNNs)، لتعزيز كفاءة التدريب والصلابة في نمذجة خصائص الأجهزة.
مقدمة
في مقدمة هذه الورقة البحثية، يناقش المؤلفون التلدين الكمي (QA) كطريقة لحل مشاكل التحسين من خلال تقليل حالات الطاقة لنظام كمي. يركزون بشكل خاص على صياغة تحسين ثنائية غير مقيدة تربيعية (QUBO)، والتي، على الرغم من قابليتها العامة، تواجه تحديات بسبب الطوبولوجيات المحددة وترابط وحدات المعالجة الكمومية (QPUs). تم تحديد عملية التضمين الثانوي (ME)، الضرورية لتكييف مشاكل التحسين لتناسب قيود QPU، كعنق زجاجة حسابي كبير، وغالبًا ما تتطلب وقتًا أكثر من التلدين الكمي نفسه. الأساليب الحالية للتضمين الثانوي محدودة في المرونة والكفاءة، خاصة عند التعامل مع رسوم بيانية متنوعة ومتنوعات الأجهزة.
لمعالجة هذه القيود، يقترح المؤلفون الاستفادة من التعلم المعزز (RL) لمعالجة التضمين الثانوي كمشكلة اتخاذ قرارات متسلسلة. يقدمون وكيلًا قائمًا على تحسين السياسة القريب (PPO) مصممًا لإنشاء تضمينات ثانوية، بالإضافة إلى استراتيجيات تحسين البيانات لتعزيز كفاءة التعلم والصلابة. تقدم الورقة تحليلًا مقارنًا لجودة التضمين الثانوي عبر نوعين من الطوبولوجيات الكمومية، كيميرا وزيفير، مما يوضح أن التعلم المعزز يمكن أن ينتج تضمينات صالحة وفعالة، خاصة في الهياكل الحديثة. تؤكد النتائج على إمكانيات التعلم المعزز كإطار متعدد الاستخدامات لمعالجة تحديات التضمين الثانوي في QA، مع الاعتراف أيضًا بحدود الطريقة واقتراح سبل للبحث المستقبلي.
الطرق
تحدد هذه القسم المنهجية المستخدمة في البحث، مع التركيز على طرق الممثل-الناقد ضمن التعلم المعزز (RL). تستخدم طرق الممثل-الناقد مكونين متميزين: الممثل، الذي يختار الإجراءات بناءً على سياسة محددة $\pi(a|s)$، والناقد، الذي يقيم قيمة الحالات أو أزواج الحالة-الإجراء. الهدف هو تحسين السياسة $\pi^*$ لتعظيم المكافأة التراكمية المتوقعة، أو العائد $G_t = \sum_{k=0}^{T-t} \gamma^k r_{t+k+1}$، حيث $\gamma$ هو عامل الخصم. يتم تحديد الممثل بواسطة $\theta$ ويمثل مباشرة السياسة، بينما يقدر الناقد، المحدد بواسطة $\phi$، دالة القيمة $v_\pi(s)$ أو دالة قيمة الحالة-الإجراء $q_\pi(s, a)$. تُستخدم دالة الميزة $A_\pi(s, a) = q_\pi(s, a) – v_\pi(s)$ لتوجيه السياسة نحو الإجراءات المثلى من خلال تعزيز تلك التي تتمتع بمزايا إيجابية.
يهدف البروتوكول التجريبي إلى تقييم فعالية نموذج التعلم المعزز في سيناريوهين: التضمين الثانوي (ME) لرسوم بيانية للمشاكل المتصلة بالكامل والرسوم البيانية التي تم إنشاؤها عشوائيًا. في السيناريو المتصل بالكامل، يتم تدريب الوكيل لأداء ME لرسم بياني محدد $G$ على رسم بياني للطوبولوجيا $H$. في سيناريو الرسم البياني العشوائي، يتم تدريب الوكلاء على رسوم بيانية متنوعة $G$ بأحجام وكثافات مختلفة، مع الحفاظ على أحجام الرسوم البيانية المتسقة (3 إلى 10 عقد). يتم إنشاء رسم بياني للطوبولوجيا $H$ بناءً على عدد خلايا الوحدة لكل جانب، مع نوعين محددين من الطوبولوجيا—كيميرا وزيفير—تتراوح من 32 إلى 2048 و160 إلى 2176 عقدة، على التوالي. تم اختيار هذه الطوبولوجيات لضمان القابلية للمقارنة في عدد الكيوبتات أثناء التجارب.
النتائج
في قسم النتائج والمناقشة، يقدم المؤلفون النتائج من تحليلهم التجريبي عبر سيناريوهين: الرسوم البيانية المتصلة بالكامل والرسوم البيانية التي تم إنشاؤها عشوائيًا. بالنسبة للرسوم البيانية المتصلة بالكامل، يستخدمون نوعين من الطوبولوجيا، كيميرا وزيفير، ويقدمون نتائج مفصلة لكل منهما. تم توثيق نتائج التضمين الثانوي للرسوم البيانية المتصلة بالكامل على طوبولوجيا كيميرا في الجدول 4 (لأحجام الرسوم البيانية |G| = 3 إلى 6) والجدول 5 (لـ |G| = 7 إلى 10). وبالمثل، يتم تقديم النتائج لطوبولوجيا زيفير في الجدول 6 (لـ |G| = 3 إلى 6) والجدول 7 (لـ |G| = 7 إلى 10).
في سيناريو الرسم البياني العشوائي، يركز القسم بشكل حصري على طوبولوجيا زيفير. يبرز القسم التحليل المقارن للطوبولوجيتين من حيث أدائهما في تضمين الرسوم البيانية المتصلة بالكامل، مع تسليط الضوء على تداعيات هذه النتائج للبحث المستقبلي والتطبيقات في نظرية الرسوم البيانية وتصميم الشبكات.
المناقشة
يناقش القسم التلدين الكمي (QA) كخوارزمية كمية لحل مشاكل التحسين التوافقي من خلال تقليل دالة الطاقة الممثلة بواسطة هاملتونيان. تبدأ العملية بهاملتونيان بسيط \( H_0 \) وتتطور إلى هاملتونيان المشكلة \( H_P \) من خلال هاملتونيان يعتمد على الزمن \( H(t) = (1 – s(t))H_0 + s(t)H_P \)، حيث \( s(t) \) هو دالة تزداد بشكل أحادي. عادةً ما يتم تأطير مشكلة التحسين كمشكلة تحسين ثنائية غير مقيدة تربيعية (QUBO)، والتي يمكن تخطيطها إلى هاملتونيان إيسينغ. يعد هذا التخطيط أمرًا حيويًا لتنفيذ QA على الأجهزة الكمومية، مما يتطلب عملية تسمى التضمين الثانوي (ME) لاستيعاب قيود الاتصال الفيزيائي للكيوبتات.
يتضمن التضمين الثانوي تمثيل مشكلة التحسين كرسوم بيانية وتحويلها لتناسب طوبولوجيا الأجهزة. يمكن أن تؤدي هذه التحويلات إلى استخدام سلاسل طويلة من الكيوبتات، مما قد يقدم تحديات مثل انقطاع السلاسل، مما قد يؤدي إلى حلول دون المستوى الأمثل. تعتبر فعالية التضمين الثانوي أمرًا حاسمًا، حيث إنها NP-hard وغالبًا ما تتطلب طرقًا هيورية للتنفيذ العملي. يبرز القسم أيضًا استخدام أداة minorminer، التي تستخدم خوارزمية عشوائية لتسهيل التضمين الثانوي، على الرغم من أنها لا تضمن حلولًا مثلى وتكون حساسة لترتيب متغيرات المشكلة. تنتقل المناقشة إلى التعلم المعزز (RL) كنهج واعد لتعزيز التضمين الثانوي، مستفيدة من خوارزميات مثل تحسين السياسة القريب (PPO) لتعيين متغيرات المشكلة بشكل تكراري إلى الكيوبتات مع إدارة مساحة الإجراءات ودوال المكافأة لتحسين عملية التضمين.
DOI: https://doi.org/10.1007/s42484-026-00341-4
Publication Date: 2026-02-19
Author(s): Riccardo Nembrini et al.
Primary Topic: Quantum Computing Algorithms and Architecture
Overview
This research investigates the application of Reinforcement Learning (RL) for minor embedding in Quantum Annealing (QA), specifically addressing the challenges associated with mapping Quadratic Unconstrained Binary Optimization (QUBO) problems onto quantum hardware. The authors propose a Proximal Policy Optimization agent that learns to create minor embeddings through a sequential decision-making process. The study evaluates the agent’s performance on both fully connected and randomly generated problem graphs across two hardware topologies: Chimera and Zephyr. Results indicate that the RL-based approach consistently yields valid minor embeddings, particularly excelling on the Zephyr topology, which features higher qubit connectivity.
In the conclusion, the authors acknowledge the RL agent’s success in learning minor embedding strategies for smaller graphs but note its limitations with larger graphs, especially on the older Chimera topology, where the qubit requirements often exceed those of existing heuristics like minorminer. The introduction of data augmentations, such as random graph permutations, significantly improved performance for randomly generated graphs. However, the agent architecture struggled to fully leverage the structural properties of the graphs, suggesting a need for further exploration of alternative architectures, such as Graph Neural Networks (GNNs), to enhance training efficiency and robustness in modeling hardware characteristics.
Introduction
In the introduction of this research paper, the authors discuss Quantum Annealing (QA) as a method for solving optimization problems by minimizing energy states of a quantum system. Specifically, they focus on the Quadratic Unconstrained Binary Optimization (QUBO) formulation, which, despite its general applicability, faces challenges due to the specific topologies and connectivity of Quantum Processing Units (QPUs). The process of Minor Embedding (ME), necessary for adapting optimization problems to fit QPU constraints, is identified as a significant computational bottleneck, often requiring more time than the quantum annealing itself. Existing heuristics for ME are limited in flexibility and efficiency, particularly when dealing with diverse problem graphs and hardware variations.
To address these limitations, the authors propose leveraging Reinforcement Learning (RL) to treat minor embedding as a sequential decision-making problem. They introduce a Proximal Policy Optimization (PPO) based agent designed to generate minor embeddings, along with data augmentation strategies to enhance learning efficiency and robustness. The paper presents a comparative analysis of minor embedding quality across two quantum hardware topologies, Chimera and Zephyr, demonstrating that RL can yield valid and efficient embeddings, particularly in modern architectures. The findings underscore the potential of RL as a versatile framework for tackling minor embedding challenges in QA, while also acknowledging the method’s limitations and suggesting avenues for future research.
Methods
The section outlines the methodology employed in the research, focusing on actor-critic methods within reinforcement learning (RL). Actor-critic methods utilize two distinct components: the actor, which selects actions based on a defined policy $\pi(a|s)$, and the critic, which evaluates the value of states or state-action pairs. The objective is to optimize the policy $\pi^*$ to maximize the expected cumulative reward, or return $G_t = \sum_{k=0}^{T-t} \gamma^k r_{t+k+1}$, where $\gamma$ is a discount factor. The actor is parameterized by $\theta$ and directly represents the policy, while the critic, parameterized by $\phi$, estimates the value function $v_\pi(s)$ or the state-action value function $q_\pi(s, a)$. The advantage function $A_\pi(s, a) = q_\pi(s, a) – v_\pi(s)$ is used to guide the policy towards optimal actions by reinforcing those with positive advantages.
The experimental protocol aims to evaluate the RL model’s effectiveness in two scenarios: minor embedding (ME) of fully connected problem graphs and randomly generated graphs. In the fully connected scenario, the agent is trained to perform ME of a specific graph $G$ onto a topology graph $H$. In the random graph scenario, agents are trained on various problem graphs $G$ of differing sizes and densities, maintaining consistent graph sizes (3 to 10 nodes). The hardware topology graph $H$ is generated based on the number of unit cells per side, with two specific topologies—Chimera and Zephyr—ranging from 32 to 2048 and 160 to 2176 nodes, respectively. These topologies were selected to ensure comparability in the number of qubits during the experiments.
Results
In the Results and Discussion section, the authors present findings from their experimental analysis across two scenarios: fully connected graphs and randomly generated graphs. For the fully connected graphs, they utilize two topologies, Chimera and Zephyr, providing detailed results for each. The minor embedding results for fully connected graphs on the Chimera topology are documented in Table 4 (for graph sizes |G| = 3 to 6) and Table 5 (for |G| = 7 to 10). Similarly, results for the Zephyr topology are presented in Table 6 (for |G| = 3 to 6) and Table 7 (for |G| = 7 to 10).
In the random graph scenario, the focus is exclusively on the Zephyr topology. The section emphasizes the comparative analysis of the two topologies in terms of their performance in embedding fully connected graphs, highlighting the implications of these findings for future research and applications in graph theory and network design.
Discussion
The section discusses Quantum Annealing (QA) as a quantum algorithm for solving combinatorial optimization problems by minimizing an energy function represented by a Hamiltonian. The process begins with a simple Hamiltonian \( H_0 \) and evolves to a problem Hamiltonian \( H_P \) through a time-dependent Hamiltonian \( H(t) = (1 – s(t))H_0 + s(t)H_P \), where \( s(t) \) is a monotonically increasing function. The optimization problem is typically framed as a Quadratic Unconstrained Binary Optimization (QUBO) problem, which can be mapped to an Ising Hamiltonian. This mapping is crucial for implementing QA on quantum hardware, which necessitates a process called Minor Embedding (ME) to accommodate the physical connectivity constraints of the qubits.
Minor Embedding involves representing the optimization problem as a graph and transforming it to fit the hardware’s topology. This transformation can lead to the use of long chains of qubits, which may introduce challenges such as chain breaks, potentially resulting in suboptimal solutions. The effectiveness of minor embedding is critical, as it is NP-hard and often requires heuristic methods for practical implementation. The section also highlights the use of the minorminer tool, which employs a stochastic algorithm to facilitate minor embedding, although it does not guarantee optimal solutions and is sensitive to the order of problem variables. The discussion transitions to Reinforcement Learning (RL) as a promising approach to enhance minor embedding, leveraging algorithms like Proximal Policy Optimization (PPO) to iteratively assign problem variables to qubits while managing the action space and reward functions to optimize the embedding process.