udm.mwis_solver

udm.mwis_solver#

Functions for mapping QUBO and related problems to unit disk graphs.

This module implements various functions for mapping QUBO (Quadratic Unconstrained Binary Optimization) problems to weighted maximum independent set problems on unit disk graphs.

Classes#

QUBOResult

Result of mapping a QUBO problem to a unit disk graph.

Ising_UnitDiskGraph

A representation of an Ising model as a unit disk graph suitable for neutral atom quantum computers.

Functions#

glue(grid, DI, DJ)

Glue multiple blocks into a whole.

crossing_lattice(g, ordered_vertices)

Create a crossing lattice from a graph.

complete_graph(n)

Create a complete graph with n nodes.

render_grid(cl[, delta])

Render a grid from a crossing lattice.

post_process_grid(grid, h0, h1)

Process the grid to add weights for 0 and 1 states based on bias vector.

map_config_back(res, cfg[, binary])

Map a configuration back from the unit disk graph to the original graph.

qubo_result_to_networkx(qubo_result)

Convert a QUBOResult to a networkx graph for MWIS solving.

map_qubo(J, h[, delta_overwrite])

Map a QUBO problem to a weighted MIS problem on a defected King's graph.

Module Contents#

glue(grid, DI: int, DJ: int)#

Glue multiple blocks into a whole.

Parameters:

  • grid – A 2D array of SimpleCell matrices

  • DI – The overlap in rows between two adjacent blocks

  • DJ – The overlap in columns between two adjacent blocks

Returns:

A matrix of SimpleCells created by gluing together the input grid

crossing_lattice(g, ordered_vertices)#

Create a crossing lattice from a graph.

Parameters:

  • g – A networkx graph

  • ordered_vertices – List of vertices in desired order

Returns:

A CrossingLattice object

complete_graph(n)#

Create a complete graph with n nodes.

render_grid(cl, delta=1)#

Render a grid from a crossing lattice.

Parameters:

  • cl – A CrossingLattice object

  • delta – delta value for the gadget weight, need to satisfy the constraint Eq. B3 of the paper

Returns:

A 2D numpy array of SimpleCell matrices

post_process_grid(grid, h0, h1)#

Process the grid to add weights for 0 and 1 states based on bias vector.

In QUBO problems, we have a Hamiltonian of the form: E(z) = -∑(i<j) J_ij z_i z_j + ∑_i h_i z_i

The bias vector h represents the linear terms h_i in the Hamiltonian. For each pin (representing a variable), we need to add the corresponding bias value to adjust the weight.

Parameters:

  • grid – Matrix of SimpleCells

  • h0 – Onsite bias for 0 state (h itself)

  • h1 – Onsite bias for 1 state (-h)

Returns:

Tuple of (GridGraph, pins list)

class QUBOResult(grid_graph, pins, mis_overhead)#

Result of mapping a QUBO problem to a unit disk graph.

grid_graph#
pins#
mis_overhead#
qubo_grid_to_locations(scale=5.0) → list[tuple[float, float]]#

Convert a QUBO grid graph to a list of tuples, each represent the node location. :param qubo_result: QUBOResult object from map_qubo

Returns:

List of (x, y) tuples

qubo_result_to_weights() → list[float]#

Convert a QUBOResult to a list of weights for each node.

Parameters:

qubo_result – QUBOResult object from map_qubo

Returns:

List of weights for each node in the grid graph.

map_config_back(res, cfg, binary=False)#

Map a configuration back from the unit disk graph to the original graph.

Parameters:

  • res – A QUBOResult, WMISResult, or similar result object

  • cfg – Configuration vector from the unit disk graph

  • binary – If True, return {0,1} variables, otherwise return {-1,1} variables

Returns:

Configuration for the original problem

qubo_result_to_networkx(qubo_result)#

Convert a QUBOResult to a networkx graph for MWIS solving.

Parameters:

qubo_result – QUBOResult object from map_qubo

Returns:

networkx Graph with weights on nodes

map_qubo(J, h, delta_overwrite=None)#

Map a QUBO problem to a weighted MIS problem on a defected King’s graph.

A QUBO problem is defined by the Hamiltonian: E(z) = -∑(i<j) J_ij z_i z_j + ∑_i h_i z_i

The mapping creates a crossing lattice with QUBO gadgets at each crossing. Each QUBO gadget has the structure: ⋅ ⋅ ● ⋅ ● A B ⋅ ⋅ C D ● ⋅ ● ⋅ ⋅

Where: - A = -J_{ij} + 4 - B = J_{ij} + 4 - C = J_{ij} + 4 - D = -J_{ij} + 4

Parameters:

  • J – Coupling matrix (must be symmetric)

  • h – Vector of onsite terms

Returns:

QUBOResult object containing the mapped problem

class Ising_UnitDiskGraph#

A representation of an Ising model as a unit disk graph suitable for neutral atom quantum computers.

This class wraps the UDM module to map QUBO/Ising problems to unit disk graphs.

ising_model: qamomile.core.ising_qubo.IsingModel#
property qubo_result: QUBOResult#

Get the QUBOResult object from the UDM module.

property networkx_graph: object#

Get the NetworkX graph representation.

property pins: list#

Get the list of pins (indices of nodes corresponding to original variables).

property nodes: list#

Get the list of nodes in the unit disk graph.

property delta: float#

Get the delta parameter used for scaling the weights.