qubosolver.embedding

Embedding algorithms for mapping QUBO variables onto quantum hardware registers.

Modules:

blade –

BLaDE (Balanced Layout and Distance Embedding) adapter for QUBO instances.
greedy_layout –

Greedy layout-based embedding algorithm for QUBO instances.

Classes:

Lattice –

Type of lattice used by the greedy_layout embedding algorithm.

Lattice

Type of lattice used by the greedy_layout embedding algorithm.

Attributes:

SQUARE –

Arrange qubits on a square lattice grid.
TRIANGULAR –

Arrange qubits on a triangular lattice grid.

SQUARE `class-attribute` `instance-attribute`

SQUARE = 'square'

Arrange qubits on a square lattice grid.

TRIANGULAR `class-attribute` `instance-attribute`

TRIANGULAR = 'triangular'

Arrange qubits on a triangular lattice grid.

qubosolver.embedding.blade

BLaDE (Balanced Layout and Distance Embedding) adapter for QUBO instances.

This module is a thin wrapper around qoolqit.embedding.Blade that exposes a single [embed] entry point accepting an Instance and returning a qoolqit.Register ready for use in a quantum program.

BLaDE maps the QUBO coefficient matrix onto a 2-D (or higher-dimensional) set of atom positions so that the physical interaction strengths (∝ 1/‖rᵢ - rⱼ‖⁶) are as proportional to the QUBO edge weights as possible. It does so by iteratively refining coordinates across multiple dimensional reduction rounds.

Classes:

Config –

qoolqit.embedding.BladeConfig with an optional MDS initialization.

Functions:

embed –

Embed a QUBO instance using the BLaDE algorithm.
embed_for_device –

Embed a QUBO instance using the BLaDE algorithm, sized for device.

Config `dataclass`

Config(dimensions: tuple[int, ...] = (6, 5, 4, 3, 2, 2, 2), compute_weight_relative_threshold: Callable[[float], float] = _constant_weight_relative_threshold, compute_regulation_cursor: Callable[[float], float] = _constant_regulation_cursor, initialize_with_mds: bool = True)

qoolqit.embedding.BladeConfig with an optional MDS initialization.

Its defaults were tuned on a benchmark of native QUBO instances: BLaDE starts from an MDS of the QUBO and explores the dimensions (6, 5, 4, 3, 2, 2, 2), with a constant weight relative threshold of 0.1 and a constant regulation cursor of 0.5.

Attributes:

initialize_with_mds (bool) –

Whether BLaDE starts from a multi-dimensional scaling (MDS) of the QUBO. MDS is skipped when starting_positions is set, and for instances without positive off-diagonal coefficient. Defaults to True.

Warning

max_min_dist_ratio is an advanced parameter: set it manually (or via the device constructor argument) with care, since a bad value can produce a register that the target device cannot realize.

embed

embed(instance: Instance, *, config: Config | None = None) -> qoolqit.Register

Embed a QUBO instance using the BLaDE algorithm.

Runs the BLaDE optimization on the QUBO coefficient matrix. Atom labels are assigned as integer indices (0, 1, …) matching the variable ordering of the QUBO matrix.

Warning

A poorly chosen config can produce a register that is incompatible with a target device. See Config.

Parameters:

instance (Instance) –

The QUBO instance to embed.
config (Config | None, default: None ) –

BLaDE configuration controlling the optimization (number of steps per round, initial atom positions, dimension sequence, maximum allowed ratio of radial to minimum distance, etc.).

Returns:

qoolqit.Register –

A register mapping each atom label to its 2-D position, with atom positions determined by BLaDE.

Raises:

ValueError –

If instance has no variables (size == 0), since a register must contain at least one qubit.
ValueError –

If the QUBO coefficient matrix has negative off-diagonal coefficients, since BLaDE cannot embed such instances.

Source code in qubosolver/embedding/blade.py

def embed(
    instance: Instance,
    *,
    config: Config | None = None,
) -> qoolqit.Register:
    """Embed a QUBO instance using the BLaDE algorithm.

    Runs the BLaDE optimization on the QUBO coefficient matrix. Atom
    labels are assigned as integer indices (``0``, ``1``, …)
    matching the variable ordering of the QUBO matrix.

    Warning:
        A poorly chosen `config` can produce a register that is incompatible
        with a target device. See [`Config`][].

    Args:
        instance: The QUBO instance to embed.
        config: BLaDE configuration controlling the optimization (number of
            steps per round, initial atom positions, dimension sequence,
            maximum allowed ratio of radial to minimum distance, etc.).

    Returns:
        A register mapping each atom label to its 2-D position, with atom positions
            determined by BLaDE.

    Raises:
        ValueError: If `instance` has no variables (``size == 0``), since a
            register must contain at least one qubit.
        ValueError: If the QUBO coefficient matrix has negative off-diagonal
            coefficients, since BLaDE cannot embed such instances.
    """
    config = config or Config()
    logger.debug("embed: instance size=%d, config=%r", instance.size, config)
    if not instance:
        raise ValueError("Cannot embed an empty instance (size=0): nothing to place.")

    if _has_negative_offdiagonal(instance.matrix):
        raise ValueError("QUBOs with negative off-diagonal coefficients cannot be embedded.")

    if instance.size == 1:
        # A single atom has no off-diagonal term to place it relative to,
        # so it is placed at the origin without running the algorithm.
        return qoolqit.Register.from_coordinates(tensor.zeros(1, 2))

    qubo = instance.matrix.numpy()

    blade_config = config._to_qoolqit()
    if config.initialize_with_mds:
        if blade_config.starting_positions is not None:
            logger.info("`starting_positions` is set: skipping the MDS initialization.")
        elif (np.triu(qubo, k=1) > 0).any():
            blade_config.starting_positions = embed_mds(qubo)

    _blade = Blade(blade_config)
    graph = _blade.embed(qubo)
    register = qoolqit.Register.from_graph(graph)
    return register

embed_for_device

embed_for_device(instance: Instance, device: qoolqit.Device) -> qoolqit.Register

Embed a QUBO instance using the BLaDE algorithm, sized for device.

Convenience wrapper around embed that derives Config.max_min_dist_ratio from device via Config's device constructor argument.

Parameters:

instance (Instance) –

The QUBO instance to embed.
device (qoolqit.Device) –

Target quantum device the resulting register must fit.

Returns:

qoolqit.Register –

A register mapping each atom label to its 2-D position, with atom positions determined by BLaDE.

To also tune device-independent parameters (e.g. dimensions or steps_per_round), pass them directly to Config alongside device:

Example

config = Config(device=device, steps_per_round=100)
register = embed(instance, config=config)

Source code in qubosolver/embedding/blade.py

def embed_for_device(
    instance: Instance,
    device: qoolqit.Device,
) -> qoolqit.Register:
    """Embed a QUBO instance using the BLaDE algorithm, sized for *device*.

    Convenience wrapper around `embed` that derives `Config.max_min_dist_ratio`
    from *device* via `Config`'s `device` constructor argument.

    Args:
        instance: The QUBO instance to embed.
        device: Target quantum device the resulting register must fit.

    Returns:
        A register mapping each atom label to its 2-D position, with atom positions
            determined by BLaDE.

    To also tune device-independent parameters (e.g. `dimensions` or
    `steps_per_round`), pass them directly to `Config` alongside `device`:

    Example:
        ```python
        config = Config(device=device, steps_per_round=100)
        register = embed(instance, config=config)
        ```
    """
    logger.debug("embed_for_device: instance size=%d, device=%r", instance.size, device)
    return embed(instance, config=Config(device=device))

qubosolver.embedding.greedy_layout

Greedy layout-based embedding algorithm for QUBO instances.

The greedy algorithm places logical QUBO nodes one at a time onto trap sites of a pre-defined lattice (triangular or square), choosing at each step the (node, trap) pair that minimizes the incremental mismatch between the QUBO coefficient matrix and the physical interaction matrix (∝ 1/‖rᵢ - rⱼ‖⁶).

Classes:

Config –

Configuration for the greedy layout embedding algorithm.

Functions:

embed –

Embed a QUBO instance using the greedy layout-based algorithm.
embed_for_device –

Embed a QUBO instance using the greedy layout-based algorithm, sized for device.

Config `dataclass`

Config(traps: int = 200, max_min_dist_ratio: float = float('inf'), max_possible_term: tuple[Literal['quantile', 'factor'], float] | float = ('quantile', 0.95), lattice: Lattice = Lattice.TRIANGULAR, p: Literal[1, 2] = 1)

Configuration for the greedy layout embedding algorithm.

Use Config.from_device to derive traps and max_min_dist_ratio from a device's constraints instead of setting them by hand.

Warning

traps and max_min_dist_ratio are advanced parameters: set them manually (or overwrite them after calling from_device) with care, since a bad value can produce a register that the target device cannot realize.

Attributes:

traps (int) –

Number of trap sites in the layout.
max_possible_term (tuple[Literal['quantile', 'factor'], float] | float) –
Largest QUBO interaction term representable at the minimum trap-trap distance, in adimensional units. One of:
- ('quantile', q): the q quantile (in [0, 1]) of the QUBO instance's strictly positive off-diagonal coefficients.
- ('factor', f): f times the QUBO instance's largest off-diagonal coefficient.
- A float, used directly.
The corresponding spacing is max_possible_term ** (-1 / 6), since interactions scale as 1 / distance ** 6.
lattice (Lattice) –

Lattice pattern (square or triangular).
max_min_dist_ratio (float) –

Maximum allowed ratio between the largest and the smallest inter-atom distance in the resulting register.
p (Literal[1, 2]) –

Order of the norm minimized when making the QUBO coefficients approach the physical interactions through ‖U - Q‖_p. p = 1 sums absolute deviations and spreads the error evenly; p = 2 penalizes large individual errors more. Defaults to 1.

Methods:

__post_init__ –

Initialize the private animation-related attributes.
from_device –

Create a Config with traps and max_min_dist_ratio derived from device.

__post_init__

__post_init__() -> None

Initialize the private animation-related attributes.

Source code in qubosolver/embedding/greedy_layout.py

def __post_init__(self) -> None:
    """Initialize the private animation-related attributes."""
    self._draw_steps: bool = False
    self._animation_save_path: pathlib.Path | None = None

from_device `staticmethod`

from_device(device: qoolqit.Device) -> Config

Create a Config with traps and max_min_dist_ratio derived from device.

Use this to size the embedding to what device actually supports. All fields can be overwritten on the returned instance.

Parameters:

device (qoolqit.Device) –

Target quantum device to derive the layout constraints from.

Returns:

Config –

A configuration with device-derived traps and max_min_dist_ratio.

Source code in qubosolver/embedding/greedy_layout.py

@staticmethod
def from_device(device: qoolqit.Device) -> Config:
    """Create a [`Config`][] with `traps` and `max_min_dist_ratio` derived from *device*.

    Use this to size the embedding to what *device* actually supports.
    All fields can be overwritten on the returned instance.

    Args:
        device: Target quantum device to derive the layout constraints from.

    Returns:
        A configuration with device-derived `traps` and `max_min_dist_ratio`.
    """
    return Config(
        traps=_number_of_traps_from_device(device),
        max_min_dist_ratio=_max_min_distance_ratio(device),
    )

embed

embed(instance: Instance, *, config: Config | None = None) -> qoolqit.Register

Embed a QUBO instance using the greedy layout-based algorithm.

The algorithm operates entirely in adimensional units (interactions scale as 1 / distance ** 6), so the coordinates it returns are already final and require no post-hoc rescaling.

Warning

A poorly chosen config can produce a register that is incompatible with a target device. See Config.

Parameters:

instance (Instance) –

The QUBO instance to embed. Its matrix attribute drives the greedy cost function.
config (Config | None, default: None ) –

Greedy embedding parameters, fully resolved (see Config.from_device for deriving traps and max_min_dist_ratio from a device). max_min_dist_ratio bounds the ratio between the largest and the smallest inter-atom distance in the resulting register.

Returns:

qoolqit.Register –

A register mapping each atom to a 2-D position.

Raises:

ValueError –

If instance has no variables (size == 0), since a register must contain at least one qubit. If the resolved trap count is less than instance.size (i.e. there are not enough trap sites for all QUBO variables).

Source code in qubosolver/embedding/greedy_layout.py

def embed(
    instance: Instance,
    *,
    config: Config | None = None,
) -> qoolqit.Register:
    """Embed a QUBO instance using the greedy layout-based algorithm.

    The algorithm operates entirely in adimensional units (interactions
    scale as ``1 / distance ** 6``), so the coordinates it returns are already
    final and require no post-hoc rescaling.

    Warning:
        A poorly chosen `config` can produce a register that is incompatible
        with a target device. See [`Config`][].

    Args:
        instance: The QUBO instance to embed.  Its ``matrix`` attribute drives
            the greedy cost function.
        config: Greedy embedding parameters, fully resolved (see [`Config.from_device`][]
            for deriving `traps` and `max_min_dist_ratio` from a device).
            ``max_min_dist_ratio`` bounds the ratio between the largest and
            the smallest inter-atom distance in the resulting register.

    Returns:
        A register mapping each atom to a 2-D position.

    Raises:
        ValueError: If `instance` has no variables (``size == 0``), since a
            register must contain at least one qubit. If the resolved trap
            count is less than ``instance.size`` (i.e. there are not enough
            trap sites for all QUBO variables).
    """
    config = config or Config()
    logger.debug("embed: instance size=%d, config=%r", instance.size, config)
    if not instance:
        raise ValueError("Cannot embed an empty instance (size=0): nothing to place.")

    if _has_negative_offdiagonal(instance.matrix):
        raise ValueError("QUBOs with negative off-diagonal coefficients cannot be embedded.")

    if config.traps < instance.size:
        raise ValueError(
            "Number of traps must be at least equal to the number of atoms on the register."
        )

    if instance.size == 1:
        # A single atom has no off-diagonal term to place it relative to,
        # so it is placed at the origin without running the algorithm.
        return qoolqit.Register.from_coordinates(tensor.zeros(1, 2))

    # spacing between adjacent trap sites, derived from the largest QUBO term
    # so that it is exactly representable at the minimum trap-trap distance
    # (interactions scale as 1 / distance ** 6).
    max_possible_term = _resolve_max_possible_term(config.max_possible_term, instance)
    spacing = max_possible_term ** (-1 / 6)

    # build params for the Greedy algorithm
    params = {
        "layout": config.lattice,
        "traps": config.traps,
        "spacing": spacing,
        "p": config.p,
        # animation controls (all read by Greedy)
        "draw_steps": config._draw_steps,  # collect per-step data
        "animation": config._draw_steps,  # render animation after run
        "animation_save_path": config._animation_save_path,  # optional export
    }

    # --- Call Greedy (unchanged public signature)
    _, coords = greedy.Greedy().launch_greedy(
        Q=instance.matrix,
        max_min_dist_ratio=config.max_min_dist_ratio,
        params=params,
    )
    register = qoolqit.Register.from_coordinates(coords)
    return register

embed_for_device

embed_for_device(instance: Instance, device: qoolqit.Device) -> qoolqit.Register

Embed a QUBO instance using the greedy layout-based algorithm, sized for device.

Convenience wrapper around embed that derives Config.traps and Config.max_min_dist_ratio from device via Config.from_device.

Parameters:

instance (Instance) –

The QUBO instance to embed.
device (qoolqit.Device) –

Target quantum device the resulting register must fit.

Returns:

qoolqit.Register –

A register mapping each atom to a 2-D position.

To also tune device-independent parameters (e.g. lattice or max_possible_term), combine Config.from_device with embed directly:

Example

config = Config.from_device(device)
config.lattice = Lattice.SQUARE
register = embed(instance, config=config)

Source code in qubosolver/embedding/greedy_layout.py

def embed_for_device(
    instance: Instance,
    device: qoolqit.Device,
) -> qoolqit.Register:
    """Embed a QUBO instance using the greedy layout-based algorithm, sized for *device*.

    Convenience wrapper around `embed` that derives `Config.traps` and
    `Config.max_min_dist_ratio` from *device* via [`Config.from_device`][].

    Args:
        instance: The QUBO instance to embed.
        device: Target quantum device the resulting register must fit.

    Returns:
        A register mapping each atom to a 2-D position.

    To also tune device-independent parameters (e.g. `lattice` or
    `max_possible_term`), combine [`Config.from_device`][] with [`embed`][]
    directly:

    Example:
        ```python
        config = Config.from_device(device)
        config.lattice = Lattice.SQUARE
        register = embed(instance, config=config)
        ```
    """
    logger.debug("embed_for_device: instance size=%d, device=%r", instance.size, device)
    return embed(instance, config=Config.from_device(device))

qubosolver.embedding

qubosolver.embedding

Lattice

SQUARE class-attribute instance-attribute

TRIANGULAR class-attribute instance-attribute

qubosolver.embedding.blade

Config dataclass

embed

embed_for_device

qubosolver.embedding.greedy_layout

Config dataclass

__post_init__

from_device staticmethod

embed

embed_for_device

SQUARE `class-attribute` `instance-attribute`

TRIANGULAR `class-attribute` `instance-attribute`

Config `dataclass`

Config `dataclass`

from_device `staticmethod`