Internals

_blade(matrix: np.ndarray, *, max_min_dist_ratio: float | None = None, dimensions: tuple[int, ...] = (5, 4, 3, 2, 2, 2), starting_positions: np.ndarray | None = None, pca: bool = False, steps_per_round: int = 200, compute_weight_relative_threshold: Callable[[float], float] = lambda _: 0.1, compute_max_distance_to_walk: Callable[[float, float | None], float | tuple[float, float, float]] = default_compute_max_distance_to_walk, compute_regulation_cursor: Callable[[float], float] = lambda _: 0.1, compute_ratio_step_factors: Callable[[float], float] = default_compute_ratio_step_factors, ratio_rerun: int = 2, draw_steps: bool | list[int] = False, draw_weighted_graph: bool = False, draw_differences: bool = False) -> np.ndarray

Embed an interaction matrix or QUBO with the BLaDE algorithm.

Note

This function is private and not part of the public API. It is documented here for internal reference only.

BLaDE stands for Balanced Latently Dimensional Embedder. It compute positions for nodes so that their interactions approach the desired values. The interactions assume that the interaction coefficient of the device is set to 1. Its typical target is on interaction matrices or QUBOs, but it can also be used for MIS with limitations if the adjacency matrix is converted into a QUBO. The general principle is based on the Fruchterman-Reingold algorithm.

Parameters:

• matrix

  (ndarray) –

  An objective interaction matrix or QUBO between the nodes. It must be either symmetrical or triangular.

• max_min_dist_ratio

  (float | None, default: None ) –

  If present, set the maximum ratio between the maximum radial distance and the minimum pairwise distances.

• dimensions

  (tuple[int, ...], default: (5, 4, 3, 2, 2, 2) ) –

  List of numbers of dimensions to explore one after the other. A list with one value is equivalent to a list containing twice the same value. For a 2D embedding, the last value should be 2. Increasing the number of intermediate dimensions can help to escape from local minima.

• starting_positions

  (ndarray | None, default: None ) –

  If provided, initial positions to start from. Otherwise, random positions will be generated. The number of dimensions of the starting positions must be lower than or equal to the first dimension to explore. If it is lower, it is added dimensions filled with random values.

• pca

  (bool, default: False ) –

  Whether to apply Principal Component Analysis to prioritize dimensions to keep when transitioning from a space to a space with fewer dimensions. It is disabled by default because it can raise an error when there are too many dimensions compared to the number of nodes.

• steps_per_round

  (int, default: 200 ) –

  Number of elementary steps to perform for each dimension transition, where at each step move vectors are computed and applied on the nodes.

• compute_weight_relative_threshold

  (Callable[[float], float], default: lambda _: 0.1 ) –

  Function that is called at each step. It takes a float number between 0 and 1 that represents the progress on the steps. It must return a float number between 0 and 1 that gives a threshold determining which weights are significant (see update_positions to learn more).

• compute_max_distance_to_walk

  (Callable[[float, float | None], float | tuple[float, float, float]], default: default_compute_max_distance_to_walk ) –

  Function that is called at each step. It takes a float number between 0 and 1 that represents the progress on the steps, and takes another argument that is set to None when max_min_dist_ratio is not enabled, otherwise, it is set to the maximum radial distance for the current step. It must return a float number that limits the distances nodes can move at one step (see update_positions to learn more).

• compute_regulation_cursor

  (Callable[[float], float], default: lambda _: 0.1 ) –

  Function that is called at each step. It takes a float number between 0 and 1 that represents the progress on the steps. It must return a float number between 0 (no regulation) and 1 (full regulation) that uniformizes the ability for the forces to achieve their objectives at each step by changing priorities.

• ratio_rerun

  (int, default: 2 ) –

  When the distance ratio constraint is not met, it defines the maximum number of times the algorithm applies additional computation steps putting the priority on the constraint.

• compute_ratio_step_factors

  (Callable[[float], float], default: default_compute_ratio_step_factors ) –

  Function that is called at the boundaries of the rounds. It defines the target ratio the enforce during the evolution. It acts as a multiplying factor on the target ratio.

• draw_steps

  (bool | list[int], default: False ) –

  If it is a boolean, it defines whether to globally enable drawing and traces for nodes and forces (for all steps). If it is a list of integers, it defines a subset of steps to enable such drawing. Requires installing the seaborn library.

• draw_weighted_graph

  (bool, default: False ) –

  For each step with drawing enabled, defines whether to draw a weighted graph representing interactions.

• draw_differences

  (bool, default: False ) –

  For each step with drawing enabled, defines whether to draw the differences between current and target interactions.

Source code in qoolqit/embedding/algorithms/blade/blade.py

def _blade(
    matrix: np.ndarray,
    *,
    max_min_dist_ratio: float | None = None,
    dimensions: tuple[int, ...] = (5, 4, 3, 2, 2, 2),
    starting_positions: np.ndarray | None = None,
    pca: bool = False,
    steps_per_round: int = 200,
    compute_weight_relative_threshold: Callable[[float], float] = (lambda _: 0.1),
    compute_max_distance_to_walk: Callable[
        [float, float | None], float | tuple[float, float, float]
    ] = default_compute_max_distance_to_walk,
    compute_regulation_cursor: Callable[[float], float] = (lambda _: 0.1),
    compute_ratio_step_factors: Callable[[float], float] = default_compute_ratio_step_factors,
    ratio_rerun: int = 2,
    draw_steps: bool | list[int] = False,
    draw_weighted_graph: bool = False,
    draw_differences: bool = False,
) -> np.ndarray:
    """Embed an interaction matrix or QUBO with the BLaDE algorithm.

    Note:
        This function is private and not part of the public API.
        It is documented here for internal reference only.

    BLaDE stands for Balanced Latently Dimensional Embedder.
    It compute positions for nodes so that their interactions
    approach the desired values. The interactions assume that the
    interaction coefficient of the device is set to 1.
    Its typical target is on interaction matrices or QUBOs, but it can also be used
    for MIS with limitations if the adjacency matrix is converted into a QUBO.
    The general principle is based on the Fruchterman-Reingold algorithm.

    Args:
        matrix: An objective interaction matrix or QUBO between the nodes. It must
            be either symmetrical or triangular.
        max_min_dist_ratio: If present, set the maximum ratio between
            the maximum radial distance and the minimum pairwise distances.
        dimensions: List of numbers of dimensions to explore one
            after the other. A list with one value is equivalent to a list containing
            twice the same value. For a 2D embedding, the last value should be 2.
            Increasing the number of intermediate dimensions can help to escape
            from local minima.
        starting_positions: If provided, initial positions to start from. Otherwise,
            random positions will be generated. The number of dimensions of the
            starting positions must be lower than or equal to the first dimension
            to explore. If it is lower, it is added dimensions filled with
            random values.
        pca: Whether to apply Principal Component Analysis to prioritize dimensions
            to keep when transitioning from a space to a space with fewer dimensions.
            It is disabled by default because it can raise an error when there are
            too many dimensions compared to the number of nodes.
        steps_per_round: Number of elementary steps to perform for each dimension
            transition, where at each step move vectors are computed and applied
            on the nodes.
        compute_weight_relative_threshold: Function that is called at each step.
            It takes a float number between 0 and 1 that represents the progress
            on the steps. It must return a float number between 0 and 1 that gives
            a threshold determining which weights are significant (see
            `update_positions` to learn more).
        compute_max_distance_to_walk: Function that is called at each step.
            It takes a float number between 0 and 1 that represents the progress
            on the steps, and takes another argument that is set to `None` when
            `max_min_dist_ratio` is not enabled, otherwise, it is set to
            the maximum radial distance for the current step.
            It must return a float number that limits the distances
            nodes can move at one step (see `update_positions` to learn more).
        compute_regulation_cursor: Function that is called at each step.
            It takes a float number between 0 and 1 that represents the progress
            on the steps. It must return a float number between 0 (no regulation)
            and 1 (full regulation) that uniformizes the ability for the forces
            to achieve their objectives at each step by changing priorities.
        ratio_rerun: When the distance ratio constraint is not met, it defines
            the maximum number of times the algorithm applies additional
            computation steps putting the priority on the constraint.
        compute_ratio_step_factors: Function that is called at the boundaries of
            the rounds. It defines the target ratio the enforce during the
            evolution. It acts as a multiplying factor on the target ratio.
        draw_steps: If it is a boolean, it defines whether to globally enable
            drawing and traces for nodes and forces (for all steps). If it is a
            list of integers, it defines a subset of steps to enable such drawing.
            Requires installing the seaborn library.
        draw_weighted_graph: For each step with drawing enabled, defines whether
            to draw a weighted graph representing interactions.
        draw_differences: For each step with drawing enabled, defines whether
            to draw the differences between current and target interactions.
    """

    if len(dimensions) == 1:
        dimensions = (dimensions[0], dimensions[0])

    assert len(dimensions) >= 2

    if isinstance(matrix, np.ndarray):
        assert not np.all(matrix == 0)
    else:
        assert not torch.all(matrix == 0)

    graph = Qubo.from_matrix(matrix).as_graph()
    matrix = np.array(
        nx.adjacency_matrix(graph, nodelist=list(range(len(matrix))), weight="weight").toarray()
    )

    if starting_positions is None:
        positions = generate_random_positions(target_interactions=matrix, dimension=dimensions[0])
    elif starting_positions.shape[1] <= dimensions[0]:
        positions = augment_dimensions_with_random_values(
            starting_positions, new_dimensions=dimensions[0] - starting_positions.shape[1]
        )
    else:
        raise ValueError(
            f"The number of dimensions in the starting positions "
            f"{starting_positions.shape[1]} is greater than the starting "
            f"number of dimensions {dimensions[0]}."
        )

    total_steps = steps_per_round * (len(dimensions) - 1)

    def step_to_progress(step: int) -> float:
        return step / (total_steps - 1)

    steps_ratios: list[float | None] = []

    if max_min_dist_ratio is not None:
        steps_ratios = [
            max_min_dist_ratio * compute_ratio_step_factors(progress)
            for progress in np.linspace(0, 1, len(dimensions))
        ]
        starting_min = _compute_min_pairwise_distance(positions)
    else:
        steps_ratios = [None] * len(dimensions)
        starting_min = None

    assert len(dimensions) == len(steps_ratios)

    def compute_weight_relative_threshold_by_step(step: int) -> float:
        return compute_weight_relative_threshold(step_to_progress(step))

    def compute_max_distance_to_walk_by_step(
        step: int, max_radial_dist: float | None
    ) -> float | tuple[float, float, float]:
        return compute_max_distance_to_walk(step_to_progress(step), max_radial_dist)

    def compute_regulation_cursor_by_step(step: int) -> float:
        return compute_regulation_cursor(step_to_progress(step))

    for dim_idx, start_ratio, final_ratio in zip(
        range(len(dimensions) - 1), steps_ratios[:-1], steps_ratios[1:]
    ):
        positions, starting_min = evolve_with_dimension_transition(
            target_interactions=matrix,
            dimensions=dimensions,
            starting_min=starting_min,
            pca=pca,
            start_step=dim_idx * steps_per_round,
            stop_step=(dim_idx + 1) * steps_per_round,
            compute_weight_relative_threshold_by_step=compute_weight_relative_threshold_by_step,
            compute_max_distance_to_walk_by_step=compute_max_distance_to_walk_by_step,
            compute_regulation_cursor_by_step=compute_regulation_cursor_by_step,
            positions=positions,
            final_ratio=final_ratio,
            dim_idx=dim_idx,
            start_ratio=start_ratio,
            draw_steps=draw_steps,
            draw_weighted_graph=draw_weighted_graph,
            draw_differences=draw_differences,
        )

    if max_min_dist_ratio is not None:
        max_radial_dist = max(np.linalg.norm(positions, axis=-1))
        min_atom_dist = _compute_min_pairwise_distance(positions)
        output_ratio = max_radial_dist / min_atom_dist
        if output_ratio > max_min_dist_ratio:

            if ratio_rerun > 0:
                return _blade(
                    matrix=matrix,
                    max_min_dist_ratio=max_min_dist_ratio,
                    dimensions=(2, 2, 2),
                    starting_positions=positions,
                    steps_per_round=steps_per_round,
                    compute_max_distance_to_walk=lambda x, max_radial_dist: 0,
                    compute_ratio_step_factors=lambda progress: np.interp(
                        progress, xp=[0, 1 / 2, 1], fp=[0.8, 0.9, 0.98]
                    ),
                    ratio_rerun=ratio_rerun - 1,
                )

            print(
                f"[Warning] Output ratio {output_ratio}"
                f" is higher than required {max_min_dist_ratio}"
            )

    return positions