Embedding Algorithm for 3D MIS Instances

This repository contains the reference implementation of a geometric embedding algorithm that maps three-dimensional constrained QUBO instances, arising from Maximum Independent Set (MIS) problems on unit disk graphs (UDGs), into two-dimensional UDGs with only nearest-neighbour interactions. The resulting 2D layouts preserve the topology of the original 3D interaction graphs and are designed to be compatible with neutral-atom quantum devices based on Rydberg-atom arrays.

---

Overview

The embedding pipeline starts from a random 3D UDG instance constructed from Sobol-distributed points in a 2D region and additional “apex” nodes representing triple overlaps of disks. The goal is to produce a 2D layout in which:

• Every node of the original 3D graph is represented.
• Every edge of the original 3D graph is realised as a nearest-neighbour edge in the 2D UDG.
• No spurious edges are created.

At a high level, the algorithm performs the following steps:

1. Instance generation in 2D and 3D

   • Sample num_nodes base points via a Sobol sequence inside a given polygon border (by default, an irregular hexagon).
   • Build a 2D unit disk graph (UDG) by connecting points whose pairwise distance is below a chosen radius.
   • Detect third-order overlaps of disks and promote them to apex nodes in a higher plane (with fixed height z = height), obtaining a 3D graph with local pyramid structures.

2. Detection of geometric structures

   • Identify all pyramid structures (one apex node connected to three base nodes forming a triangle).
   • Group pyramids into multi-pyramid structures, such as:
     • families of pyramids sharing one base node,
     • families of pyramids sharing two base nodes,
     • more complex local configurations.

3. Local embedding of pyramid structures

   • For pyramids sharing one base node, replace each 3D configuration with a 2D “bow-tie-like” gadget that realises the same connectivity using a small number of auxiliary nodes.
   • For pyramids sharing two base nodes, apply specialised gadgets suitable for edge-sharing structures.
   • When nodes are displaced by these gadgets, restore their original connections through chains of auxiliary “wire” nodes, placed at controlled distances to avoid creating unwanted edges.

4. Global layout assembly

   • Iteratively merge embedded components and remaining non-pyramid nodes into a single 2D layout by:
     • attaching components that share a node,
     • attaching components connected by a single edge,
     • adding direct neighbours of the current layout,
     • finally placing fully disconnected components and isolated nodes with suitable wire chains.
   • Throughout, enforce minimum inter-node distances and avoid creating spurious adjacency.

5. Topological consistency check

   • Perform a final consistency check to ensure that:
     • all original 3D nodes are present,
     • all original 3D edges are realised in the final 2D UDG,
     • no illegal extra edges are introduced.

The main entry point of the implementation is the function run_embedding_algorithm, which runs the full pipeline and returns both the original 3D instance and the final 2D embedding, together with diagnostic information (timings, apex list, etc.).

---

Installation

This project uses Python and the scientific Python ecosystem.

Requirements

• Python 3.13.2 or later (recommended)
• All dependencies are listed in requirements.txt.

Setup

Clone the repository:

git clone https://github.com/UniboRick/embedding-algorithm.git
cd embedding-algorithm

Create a virtual environment if needed:

python -m venv .venv
# On Linux/macOS:
source .venv/bin/activate
# On Windows:
.venv\Scripts\activate

Install the dependencies:

pip install -r requirements.txt

Usage

Command-line usage

From the repository root:

python main.py

This runs the full embedding pipeline on a random 3D UDG instance with default parameters.

The run can be customized with:

python main.py \
  --num-nodes 200 \
  --radius 1.0 \
  --height 1.0 \
  --seed 42 \
  --plot-2d \
  --plot-3d \
  --time-check \
  --verbose

Available options:

• --num-nodes Number of base nodes generated by the Sobol sequence (default: 200).

• --radius Disk radius used to build the 2D UDG and to detect overlaps (default: 1.0).

• --height z-coordinate for apex nodes in the 3D UDG (default: 1.0).

• --seed Random seed passed to the Sobol generator and point generation for reproducibility (default: None).

• --plot-2d If set, plot the initial 2D UDG instance.

• --plot-3d If set, plot the 3D UDG with apex nodes.

• --time-check If set, print timing information of the whole embedding process.

• --verbose If set, print status messages during component attachment attempts.

The script will print a concise summary of the final instance (number of nodes/edges, number of apex nodes, total time if requested).

Python API

You can also call the embedding directly from Python, for example in a notebook or another script:

from embedding_algorithm import run_embedding_algorithm

(
    sobol_points,
    G_2d,
    G_3d,
    coords_3d,
    final_pos,
    all_nodes,
    apex_list,
    total_time,
) = run_embedding_algorithm(
    num_nodes=200,
    seed=42,
    border=None,       # use default hexagon for the sampling region
    radius=1.0,
    height=1.0,
    plot_2d=False,
    plot_3d=False,
    time_check=True,
    verbose=False,
)

Returned values:

• sobol_points (dict) – mapping node → (x, y) of the generated Sobol points.
• G_2d (networkx.Graph) – 2D unit disk graph on the Sobol points.
• G_3d (networkx.Graph) – 3D graph including base nodes and apex nodes.
• coords_3d (dict) – mapping node → (x, y, z) of all nodes in G_3d.
• final_pos (dict) – mapping node → (x, y) giving the final 2D embedding.
• all_nodes (list) – sorted list of all nodes present in final_pos.
• apex_list (list) – list of apex-node identifiers created in the 3D construction.
• total_time (float or None) – total time in seconds for the embedding process (or None if time_check is False).

run_embedding_algorithm raises a ValueError if pyramids cannot be embedded, if components or edges cannot be attached/restored under the constraints, or if the final embedding fails the topological consistency check.

---

Repository structure

The repository is organised as follows:

embedding-algorithm/
  README.md              # This file
  requirements.txt       # Python dependencies
  main.py                # Command-line entry point (example usage of the pipeline)

  embedding_algorithm/   # Python package containing the implementation
    __init__.py          # Exposes run_embedding_algorithm
    embedding.py         # High-level pipeline (run_embedding_algorithm)
    generation.py        # Sobol sampling, 2D UDG construction, 3D UDG with apex nodes
    structure_search.py  # Detection and grouping of pyramids / multi-pyramid structures
    embed_one_anchor.py  # Embedding of structures with pyramids sharing one base node
    embed_two_anchor.py  # Embedding of structures with pyramids sharing two base nodes
    helpers.py           # Shared helpers: geometry, graph utilities, topology checks

You can import individual modules if you wish to access lower-level functions (e.g. for custom experiments or partial tests).

---

Thesis

This code accompanies the Master’s thesis:

Topology-Preserving Embedding of Maximum Independent Set Instances for Rydberg-Atom Quantum Optimizers [Theoretical Physics] Riccardo Vidali, Alma Mater Studiorum – University of Bologna, 2025.

The thesis' PDF is available at the institutional repository https://amslaurea.unibo.it/.

---

Citation

If you use this code, please cite:

@mastersthesis{vidali2025embedding,
  author = {Riccardo Vidali},
  title = {Topology-Preserving Embedding of Maximum Independent Set Instances for Rydberg-Atom Quantum Optimizers},
  school = {Alma Mater Studiorum -- Universit{\`a} di Bologna},
  year = {2025},
  type = {Master's thesis},
  address = {Bologna, Italy},
  url = {https://amslaurea.unibo.it/},
  note = {Available at the institutional repository of the University of Bologna}
}