This is the title slide for a Master's Thesis Presentation. The subtitle states: "Developing a Minor Embedding Algorithm for Oscillator-Based Ising Machines Using Reinforcement Learning by Shishir Siwakoti."

Master's Thesis Presentation

Developing a Minor Embedding Algorithm for Oscillator-Based Ising Machines Using Reinforcement Learning by Shishir Siwakoti

Source: Developing a Minor Embedding Algorithm for Oscillator-Based Ising Machines Using Reinforcement Learning

The slide outlines a five-part presentation agenda on oscillator-based Ising machines and reinforcement learning. It covers Motivation & Objectives, Hardware & RL Formulation, Policy & Training, Results & Comparisons, and Conclusions & Future Work.

Presentation Agenda

1. Motivation & Objectives

Title, research motivation, objectives, and problem definition.

2. Hardware & RL Formulation

Oscillator-based Ising machine model and RL problem setup.

3. Policy & Training

Policy architecture, training procedures, and evaluation methods.

4. Results & Comparisons

Experimental results, comparisons with prior approaches.

5. Conclusions & Future Work

Summary of findings and directions for future research. Source: Developing a Minor Embedding Algorithm for Oscillator-Based Ising Machines Using Reinforcement Learning by Shishir Siwakoti

Oscillator-based Ising machines efficiently solve combinatorial optimization problems, but minor embedding challenges limit their scalability. Traditional embedding methods are suboptimal, while RL enables adaptive learning for superior embeddings.

Motivation

• Oscillator-based Ising machines solve combinatorial optimization efficiently.
• Minor embedding challenges limit scalability.
• Traditional embedding methods are suboptimal.
• RL enables adaptive learning for superior embeddings.

Source: Shishir Siwakoti, Master's Thesis

The research objectives center on developing a reinforcement learning-based minor embedding algorithm optimized for oscillator-based hardware. The aims are to surpass baselines in embedding quality while minimizing solve time.

Research Objectives

• - Develop RL-based minor embedding algorithm.
• - Optimize for oscillator-based hardware.
• - Surpass baselines in embedding quality.
• - Minimize solve time versus baselines.

Source: Developing a Minor Embedding Algorithm for Oscillator-Based Ising Machines Using Reinforcement Learning by Shishir Siwakoti

This slide serves as the section header for Section 04: Problem Definition. It highlights the challenge of mapping problem graphs to oscillator-based Ising machine hardware while preserving structure amid oscillator dynamics and chain issues.

Developing a Minor Embedding Algorithm for Oscillator-Based Ising Machines Using Reinforcement Learning

04

Problem Definition

Mapping problem graphs to hardware preserving structure amid oscillator dynamics and chain challenges

Source: Master's Thesis by Shishir Siwakoti

The slide describes a hardware model as a network of coupled oscillators with programmable couplings Jij, where phases θi encode spin variables σi ≈ cos(θi). It targets optimization of the Ising Hamiltonian H = -∑{i<j} Jij σi σj - ∑i hi σi, featuring Ising spins σi, couplings Jij, and local biases hi.

Hardware Model

Source: 'Developing a Minor Embedding Algorithm for Oscillator-Based Ising Machines Using Reinforcement Learning' by Shishir Siwakoti

This slide formulates reinforcement learning as an MDP, with states as a graph plus partial embedding, actions to extend embedding chains, and rewards from quality and validity metrics. The goal is to maximize long-term reward for complete embeddings.

RL Formulation

• MDP State: Graph + partial embedding
• Actions: Extend embedding chains
• Rewards: Quality + validity metrics
• Goal: Maximize long-term reward for complete embeddings

Source: Developing a Minor Embedding Algorithm for Oscillator-Based Ising Machines Using Reinforcement Learning

The "Policy Architecture" slide depicts a model with a GNN encoder that processes adjacency matrices. It includes an actor head for predicting chain extensions and a critic head for estimating state values.

Policy Architecture

!Image

• GNN encoder processes adjacency matrices
• Actor head predicts chain extensions
• Critic head estimates state values

Source: Wikipedia: Graph neural network

The timeline details training phases: pre-training on small graphs in 2022 for basic minor embedding, and curriculum learning with increasing complexity in 2023 for scalability. Evaluation on QA benchmarks, including Ising instances up to 1000 spins, occurred in 2024.

Training and Evaluation

2022: Pre-training on Small Graphs Initial RL policy training on small graph instances to learn basic minor embedding capabilities. 2023: Curriculum Learning Phase Gradual increase in graph complexity during training for enhanced scalability and generalization. 2024: Evaluation on Benchmarks Assessed performance on Ising instances up to 1000 spins using established QA benchmarks.

Source: Developing a Minor Embedding Algorithm for Oscillator-Based Ising Machines Using Reinforcement Learning by Shishir Siwakoti

The Results slide showcases a 95%+ embedding success rate on benchmark instances. It also reports a 20% chain length reduction versus baseline methods and a 3x solve time speedup in hardware simulations.

Results

• 95%+: Embedding Success Rate

On benchmark instances

• 20%: Chain Length Reduction

Vs. baseline methods

• 3x: Solve Time Speedup

Hardware simulations Source: Developing a Minor Embedding Algorithm for Oscillator-Based Ising Machines Using Reinforcement Learning

The slide compares an RL policy to a greedy baseline and QUBO minor embedding methods. It achieves superior embedding density and resource efficiency versus the baseline, while outperforming QUBO in training convergence speed and embedding fidelity.

Comparisons

Source: Developing a Minor Embedding Algorithm for Oscillator-Based Ising Machines Using Reinforcement Learning by Shishir Siwakoti

RL enables efficient minor embedding for oscillator Ising machines, achieving state-of-the-art performance and validation on realistic hardware models. The slide concludes with "Thank you for your attention!"

Conclusions

• RL enables efficient minor embedding for oscillator Ising machines

• Achieves state-of-the-art performance
• Validates approach on realistic hardware models

Thank you for your attention!

Source: Developing a Minor Embedding Algorithm for Oscillator-Based Ising Machines Using Reinforcement Learning by Shishir Siwakoti

The "Future Work" slide outlines plans to deploy on real hardware and implement multi-graph batching. It also includes developing hybrid classical-quantum embeddings and scaling to larger problems.

Future Work

• Deploy on real hardware.
• Implement multi-graph batching.
• Develop hybrid classical-quantum embeddings.
• Scale to larger problems.

Source: Developing a Minor Embedding Algorithm for Oscillator-Based Ising Machines Using Reinforcement Learning by Shishir Siwakoti