Minor Embedding for Quantum Annealing with Reinforcement Learning

This paper proposes a Reinforcement Learning approach using Proximal Policy Optimization to automate the computationally expensive minor embedding process in Quantum Annealing, demonstrating its ability to efficiently and scalably map diverse problem graphs onto modern quantum hardware topologies like Chimera and Zephyr.

The Gist

Imagine you have a very complex puzzle, like a giant map of a city where every street connects to every other street. You want to solve this puzzle using a special, super-fast computer called a Quantum Annealer.

However, there's a catch: this super-computer doesn't have a map where every street connects to every other one. Its internal wiring is sparse, like a small town where you can only walk to your immediate neighbors.

This is the problem of Minor Embedding. You have to figure out how to fold your giant, fully-connected city map onto the small-town wiring of the computer without breaking any connections.

The Old Way: The "Guess and Check" Mapmaker

Traditionally, scientists used a set of rigid rules (heuristics) to do this folding. Think of it like a mapmaker who has a specific rulebook for folding maps.

• The Problem: The rulebook is great for one specific type of map, but if you give them a slightly different map or a new type of computer, the rules break. It's like trying to fold a square piece of paper into a circle using instructions meant for a triangle.
• The Cost: This process is slow and computationally expensive. It often takes longer to fold the map than it does for the computer to actually solve the puzzle!

The New Way: The "Smart Apprentice" (Reinforcement Learning)

This paper proposes a new approach: instead of giving the computer a rulebook, we teach it how to fold the map itself using Reinforcement Learning (RL).

Think of the AI agent as a smart apprentice trying to learn how to fold a complex origami crane.

1. The Environment: The "paper" is the problem graph, and the "table" is the quantum computer's hardware.
2. The Action: The apprentice picks up a piece of the problem (a variable) and tries to place it on the table (a qubit).
3. The Reward:
   • If the piece fits and connects to the right neighbors, the apprentice gets a small "good job" signal.
   • If they use too many pieces of paper (qubits) or create a messy chain, they get a "penalty" (a negative score).
   • The goal is to finish the folding using the fewest pieces of paper possible while keeping all connections intact.

Over thousands of attempts, the apprentice learns the best way to fold the map, not by following rigid rules, but by learning from its mistakes and successes.

The Experiment: Two Types of Tables

The researchers tested their "Smart Apprentice" on two different types of quantum computer "tables" (topologies):

1. Chimera (The Old Table): An older design where connections are limited (like a small town with few roads).
2. Zephyr (The New Table): A modern, high-tech design with many more connections (like a city with a dense highway system).

What They Found

1. The Apprentice is a Great Learner (on the New Table)
On the Zephyr table, the apprentice was amazing. Because the table had so many connections, the apprentice could easily find a way to fold the map. It succeeded almost 100% of the time and used a very efficient number of qubits. It was like the apprentice finally having a big, open table with plenty of space to work.

2. The Apprentice Struggles on the Old Table
On the Chimera table, the apprentice had a harder time. As the puzzles got bigger, the apprentice started to get confused, sometimes failing to fold the map at all or using way too many pieces of paper. This is like trying to fold a giant, complex origami crane on a tiny, cluttered desk.

3. The "Magic Mirror" Trick (Data Augmentation)
The researchers noticed that the apprentice sometimes got confused by the orientation of the table. If they rotated the table or flipped it, the apprentice thought it was a completely new problem.
To fix this, they used a trick called Data Augmentation. Imagine showing the apprentice the same puzzle, but sometimes rotated 90 degrees, sometimes flipped horizontally, and sometimes mirrored.

• Result: This didn't help much on the simple, fully-connected maps. But on random, messy maps, this trick was a game-changer. It taught the apprentice to recognize the structure of the puzzle rather than just memorizing the specific layout, allowing it to fold complex, random maps much more efficiently.

The Big Takeaway

This paper shows that Machine Learning can be a flexible, powerful tool for solving the "folding" problem in quantum computing.

• Pros: It's adaptable. Unlike rigid rulebooks, an AI can learn to handle different shapes and sizes of problems.
• Cons: The current AI (a simple neural network) has limits. It struggles when the puzzle gets too big or the "table" is too small and complex.

The Future: The authors suggest that in the future, we should upgrade the apprentice to a "Graph Neural Network"—a type of AI that naturally understands how things connect, like a human who intuitively sees how a map fits together, rather than just looking at a list of coordinates.

In short: They taught a computer to learn how to fit a square peg into a round hole (or rather, a complex graph into a sparse chip) by letting it practice, fail, and learn, rather than forcing it to follow a manual. It works great on modern hardware and holds promise for the future of quantum computing.

Technical Summary

1. Problem Statement

Quantum Annealing (QA) is a paradigm for solving combinatorial optimization problems formulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. However, physical Quantum Processing Units (QPUs), such as those from D-Wave, possess sparse connectivity topologies (e.g., Chimera, Pegasus, Zephyr) that do not natively support the fully connected or arbitrary graphs required by many QUBO problems.

To bridge this gap, Minor Embedding (ME) is required. This process maps problem variables to chains of physical qubits on the hardware graph.

• The Bottleneck: ME is an NP-hard problem. Current state-of-the-art solutions rely on heuristic algorithms (e.g., minorminer), which are computationally expensive, often scale poorly with problem size, and lack flexibility in optimizing specific objectives (e.g., minimizing chain length).
• The Gap: Existing heuristics are often static and difficult to generalize across different hardware topologies or dynamic problem structures. There is a need for a flexible, adaptive framework that can learn to construct efficient embeddings.

2. Methodology

The authors propose a Reinforcement Learning (RL) framework to treat Minor Embedding as a sequential decision-making problem.

2.1 Core Framework

• Algorithm: The agent uses Proximal Policy Optimization (PPO), an actor-critic algorithm known for stability in high-dimensional action spaces.
• Architecture: A Multi-Layer Perceptron (MLP) is used as the policy network. The authors chose MLPs for their ease of implementation and training speed, acknowledging that they lack native graph invariance (unlike Graph Neural Networks), which they address via data augmentation.
• State Representation ($s_t$): The observation vector is a 1D array composed of four parts:
  1. Available Qubits ($S_H$): Binary vector indicating free qubits on the hardware graph.
  2. Missing Links ($S_G$): Integer vector indicating how many connections remain for each problem node.
  3. Current Node ($S_R$): One-hot vector identifying the problem node currently being embedded (selected via a Round-Robin strategy).
  4. Current Chain ($S_C$): Binary vector indicating which hardware qubits currently belong to the chain of the active problem node.
• Action Space: The agent selects a single hardware qubit to add to the current problem node's chain.
• Invalid Action Masking (IAM): To constrain the combinatorial explosion of the action space, the agent is only allowed to select qubits that are:
  • Currently available.
  • Adjacent to the existing chain of the current problem node.
  • Not already assigned to other chains.

2.2 Reward Function

The reward is designed to encourage valid embeddings with minimal resource usage:

• Step Penalty: A fixed negative reward (e.g., $-0.1$) is given for every action. This incentivizes the agent to find the solution in the fewest steps (i.e., using the fewest qubits/shortest chains).
• Terminal Reward: Implicitly, the episode terminates upon successful embedding or failure.

2.3 Data Augmentation Strategies

Since the MLP cannot natively handle graph symmetries (permutation invariance), the authors introduce data augmentation to improve generalization:

• Transformations: At each training step, the hardware graph state is randomly transformed via:
  • 90° rotations.
  • Mirroring (horizontal, vertical, diagonal).
  • Permutations of vertical/horizontal nodes.
• Goal: To force the policy to learn invariant features rather than memorizing specific node indices, thereby improving robustness on randomly generated graphs.

3. Key Contributions

1. RL Formulation of ME: The first application of PPO-based RL to the Minor Embedding problem, framing it as a sequential decision process.
2. Augmentation for Symmetry: A novel set of data augmentation strategies tailored to hardware topologies (Chimera/Zephyr) to compensate for the lack of graph-equivariant architectures (like GNNs) in the current model.
3. Comprehensive Evaluation: A rigorous comparison across two distinct hardware topologies (Chimera and Zephyr) and two problem types (fully connected and randomly generated graphs).
4. Performance Analysis: Detailed metrics on Success Rate (SR) and Qubit Efficiency Ratio (QER), benchmarking against the standard minorminer heuristic.

4. Experimental Results

4.1 Fully Connected Graphs

• Chimera Topology (Older, lower connectivity):
  • Success Rate: High for small graphs ($|G| \le 6$) but drops sharply as graph size increases. The agent struggles with large, dense graphs on this sparse topology.
  • Efficiency: The agent often uses significantly more qubits than minorminer on larger hardware instances ($H_{size}$), indicating difficulty in exploring the large action space.
  • Augmentation Impact: Mixed results; sometimes improved success rates for intermediate sizes but occasionally degraded performance.
• Zephyr Topology (Newer, higher connectivity):
  • Success Rate: Achieved 100% success rate across all tested graph sizes ($|G| \le 10$) and hardware sizes.
  • Efficiency: For small to moderate graphs, the agent produces embeddings comparable to minorminer. However, for very large graphs on large hardware, the agent still tends to use more qubits than the heuristic, though the gap is smaller than on Chimera.
  • Conclusion: The higher connectivity of Zephyr (up to 20 connections per qubit vs. 6 in Chimera) significantly mitigates the agent's architectural limitations.

4.2 Randomly Generated Graphs

• Performance: The agent performs significantly better on random graphs than on fully connected ones, as the lower connectivity reduces the complexity of the embedding.
• Impact of Augmentation: Unlike the fully connected scenario, data augmentation proved highly effective when applied during both training and testing.
  • Example: For $H_{size}=8, |G|=8$, the base model required ~317 qubits, while the augmented model required only ~18 qubits.
  • This suggests that for irregular structures, learning invariance through augmentation is critical for finding compact solutions.

4.3 Training Stability

• The agent demonstrated stable convergence on smaller hardware topologies.
• On larger topologies ($H_{size}=8$), training showed initial plateaus or variance but eventually converged to effective policies, confirming that RL can learn the embedding logic despite the non-convex landscape.

5. Significance and Future Work

• Flexibility: The RL approach offers a flexible framework where reward functions can be easily modified to optimize for different metrics (e.g., chain strength, solution quality) without re-engineering the heuristic logic.
• Scalability: While the current MLP-based agent struggles with very large, dense graphs on sparse hardware, it scales well to moderate sizes and adapts well to modern, highly connected topologies like Zephyr.
• Limitations: The primary limitation is the architecture's inability to natively model graph symmetries, leading to inefficiency on large action spaces.
• Future Directions: The authors explicitly propose moving toward Graph Neural Networks (GNNs) in future work. GNNs would natively handle permutation invariance and graph structure, potentially eliminating the need for heavy data augmentation and significantly improving performance on large-scale problems.

Conclusion: This work demonstrates that Reinforcement Learning is a viable, flexible alternative to traditional heuristics for Minor Embedding, particularly on modern quantum hardware topologies. While current implementations face scaling challenges, the potential for adaptive, objective-driven embedding strategies makes this a promising direction for the future of Quantum Annealing.