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
Section titled “
_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
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
Section titled “ matrix
”ndarray)
–An objective interaction matrix or QUBO between the nodes. It must be either symmetrical or triangular.
max_min_dist_ratio
Section titled “ 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
Section titled “ 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
Section titled “ 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.
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
Section titled “ 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
Section titled “ 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
Section titled “ 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
Section titled “ 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
Section titled “ 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
Section titled “ 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
Section titled “ 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
Section titled “ draw_weighted_graph
”bool, default:False)
–For each step with drawing enabled, defines whether to draw a weighted graph representing interactions.
draw_differences
Section titled “ 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