kaiwu.preprocess package

Module contents

Module: preprocess

Function: Preprocessing-related functions, currently focusing on precision-related functions for Ising matrices

kaiwu.preprocess.calculate_qubo_matrix_bit_width(qubo_matrix, bit_width=8)

Validate the bit width of QUBO matrix elements

Convert the QUBO matrix to an Ising matrix and validate the QUBO matrix by checking the bit width of the Ising matrix elements

Args:

qubo_matrix (np.ndarray): QUBOmatrix

bit_width (int): bit width

Returns:

np.ndarray: Ising matrix that satisfies the precision requirements

Examples1:

>>> import numpy as np
>>> import kaiwu as kw
>>> _matrix = -np.array([[-480., 508., -48.],
...                      [ 508., -508., -48.],
...                      [ -48., -48., 60.]])
>>> kw.preprocess.calculate_qubo_matrix_bit_width(_matrix)
{'precision': 8, 'multiplier': np.float64(1.0)}

Example 2 (Meets requirements after scaling):

>>> import numpy as np
>>> import kaiwu as kw
>>> _matrix = -np.array([[-512.,  520.,  -48.],
...                      [ 520., -520.,  -48.],
...                      [ -48.,  -48.,   40.]])
>>> kw.preprocess.calculate_qubo_matrix_bit_width(_matrix)
{'precision': 8, 'multiplier': np.float64(0.5)}

Example 3 (Does not meet requirements even after scaling):

>>> import numpy as np
>>> import kaiwu as kw
>>> _matrix = -np.array([[-488.,  516.,  -48.],
...                      [ 516., -516.,  -48.],
...                      [ -48.,  -48.,   60.]])
>>> kw.preprocess.calculate_qubo_matrix_bit_width(_matrix)
{'precision': inf, 'multiplier': inf}

kaiwu.preprocess.adjust_qubo_matrix_precision(qubo_matrix, bit_width=8)

Adjust matrix precision, matrixprecision, matrix, matrixprecision

Args:

qubo_matrix (np.ndarray): target matrix

bit_width (int): precision range; currently only 8 bits are supported, one of which is the sign bit

Returns:

np.ndarray: QUBO matrix that satisfies the precision requirements

Examples:

>>> import numpy as np
>>> import kaiwu as kw
>>> ori_qubo_mat1 = np.array([[0.89, 0.22, 0.198],
...                      [0.22, 0.23, 0.197],
...                      [0.198, 0.197, 0.198]])
>>> qubo_mat1 = kw.preprocess.adjust_qubo_matrix_precision(ori_qubo_mat1)
>>> qubo_mat1
array([[348., 168., 152.],
       [ -0.,  92., 152.],
       [ -0.,  -0.,  80.]])
>>> ori_qubo_mat2 = np.array([[0.89, 0.22, 0.198],
...                           [0.22, 0.23, 0.197],
...                           [0.198, 0.197, 100]])
>>> qubo_mat2 = kw.preprocess.adjust_qubo_matrix_precision(ori_qubo_mat2)
>>> qubo_mat2  # The solutions obtained by qubo_mat2 and ori_qubo_mat2 matrices are quite different
array([[  8.,  -0.,  -0.],
       [ -0.,   4.,  -0.],
       [ -0.,  -0., 508.]])

kaiwu.preprocess.calculate_ising_matrix_bit_width(ising_matrix, bit_width=8)

Compute the parameter bit width of the Ising matrix

Args:

ising_matrix (np.ndarray): ising matrix

bit_width (int): maximum bit-width limit

Returns:

dict: return the precision and scaling factor of the Ising matrix

• precision (int): Ising matrix precision

• multiplier (float): scaling factor

1:

>>> import numpy as np
>>> import kaiwu as kw
>>> _matrix = -np.array([[ -0., 127., -12.,  -5.],
...                      [127.,  -0., -12., -12.],
...                      [-12., -12.,  -0.,  -9.],
...                      [ -5., -12.,  -9.,  -0.]])
>>> kw.preprocess.calculate_ising_matrix_bit_width(_matrix)
{'precision': 8, 'multiplier': np.float64(1.0)}

Example 2 (Meets requirements after scaling):

>>> import numpy as np
>>> import kaiwu as kw
>>> _matrix = -np.array([[ -0., 12.7, -1.2,  -0.5],
...                      [12.7,  -0., -1.2, -1.2],
...                      [-1.2, -1.2, -0.,   -0.9],
...                      [-0.5, -1.2, -0.9,  -0.]])
>>> kw.preprocess.calculate_ising_matrix_bit_width(_matrix)
{'precision': 8, 'multiplier': np.float64(10.0)}

Example 3 (Does not meet requirements even after scaling):

>>> import numpy as np
>>> import kaiwu as kw
>>> _matrix = -np.array([[-488.,  516.,  -48.],
...                      [ 516., -516.,  -48.],
...                      [ -48.,  -48.,   60.]])
>>> kw.preprocess.calculate_ising_matrix_bit_width(_matrix)
{'precision': inf, 'multiplier': inf}

kaiwu.preprocess.adjust_ising_matrix_precision(ising_matrix, bit_width=8)

ising matrixprecision, matrixprecision, matrix, matrixprecision

Args:

ising_matrix(np.ndarray): target matrix

bit_width(int): precision range; currently only 8 bits are supported, one of which is the sign bit

Returns:

np.ndarray: Ising matrix that satisfies the precision requirements

Examples:

>>> import numpy as np
>>> import kaiwu as kw
>>> ori_ising_mat1 = np.array([[0, 0.22, 0.198],
...                            [0.22, 0, 0.197],
...                            [0.198, 0.197, 0]])
>>> ising_mat1 = kw.preprocess.adjust_ising_matrix_precision(ori_ising_mat1)
>>> ising_mat1
array([[  0, 127, 114],
       [127,   0, 114],
       [114, 114,   0]])
>>> ori_ising_mat2 = np.array([[0, 0.22, 0.198],
...                            [0.22, 0, 50],
...                            [0.198, 50, 0]])
>>> ising_mat2 = kw.preprocess.adjust_ising_matrix_precision(ori_ising_mat2)
>>> ising_mat2  # The solutions obtained by qubo_mat2 and ori_qubo_mat2 matrices are quite different
array([[  0,   1,   1],
       [  1,   0, 127],
       [  1, 127,   0]])

class kaiwu.preprocess.PrecisionReducer(component: IsingSolver, precision=8, target_bits=None, only_feasible_solution=False, truncated_precision=20)

Bases: IsingSolver, QuboSolver

Precision reduction decorator class

Convert large-scale or high-precision Ising matrices into a form that can be solved on SPQC devices with limited bit precision by using precision reduction and matrix splitting. Truncate first, then split; if the precision still does not meet the requirement after splitting, truncate directly to the target precision.

Applicable scenarios:

• Matrix coefficient precision is too high, such as decimals like 1.23 or large values like 10000.0, and exceeds the device representation range

• The matrix scale is too large and requires split-based dimensionality reduction

Enable logs to view detailed output: kw.common.set_log_level(“DEBUG”)

Args:

component (IsingSolver): base solver, such as SimulatedAnnealingOptimizer

precision (int): target matrix precision (decimal places), controlling the precision after matrix splitting

target_bits (int): target number of matrix bits; defaults to None, meaning no control

only_feasible_solution (bool): whether to keep only feasible solutions; defaults to False.

When only_feasible_solution=True and none of the solutions is feasible, KaiwuError is raised

truncated_precision (int): truncation precision. The larger the difference from precision, the more variables are added after matrix splitting.

Example1 (Basic usage: reduce matrix precision):

>>> import numpy as np
>>> import kaiwu as kw
>>> matrix = -np.array([[0., 1.23, 0., 1., 1.],
...                     [1.23, 0., 0., 1., 1.],
...                     [0., 0., 0., 1., 1.],
...                     [1., 1., 1., 0., 1.],
...                     [1., 1., 1., 1., 0.]])
>>> optimizer = kw.classical.SimulatedAnnealingOptimizer(
...     initial_temperature=100, alpha=0.99,
...     cutoff_temperature=0.001, iterations_per_t=10
... )
>>> new_optimizer = kw.preprocess.PrecisionReducer(
...     optimizer, precision=4
... )
>>> solutions = new_optimizer.solve(matrix)

Example2 (Handle high-precision/large-coefficient matrices):

>>> matrix2 = -np.array([[0., 1.23, 0., 1., 10000.],
...                      [1.23, 0., 0., 1., 1.],
...                      [0., 0., 0., 1., 1.],
...                      [1., 1., 1., 0., 1.],
...                      [10000., 1., 1., 1., 0.]])
>>> new_optimizer2 = kw.preprocess.PrecisionReducer(
...     optimizer, precision=4, only_feasible_solution=False
... )
>>> solutions = new_optimizer2.solve(matrix2)

Example3 (Control target number of bits):

>>> new_optimizer3 = kw.preprocess.PrecisionReducer(
...     optimizer, precision=4, target_bits=10
... )

get_hamiltonian()

Returns:

hamiltonian (np.ndarray): Hamiltonian value of the current solution

on_matrix_change()

Update matrix-related information. This can be implemented when inheriting IsingSolver. When the processed Ising matrix changes, this function is called so corresponding actions can be taken

set_matrix(ising_matrix)

Set the matrix and update related data

solve(ising_matrix=None, negtail_flip=True, sort_solutions=False)

Solve the Ising matrix

Args:

ising_matrix (np.ndarray): Ising matrix

negtail_flip (bool): Whether to perform negative-tail flipping

sort_solutions (bool): Whether to sort solutions

Returns:

output (np.ndarray): solution vector

solve_qubo(*args, **kwargs)

kaiwu.preprocess.get_dynamic_range_metric(mat)

Calculate the dynamic range (DR) value

$DR(Q) = log(max_{i,j}|Q_i - Q_j|/min_{Q_i \neq Q_j}|Q_i-Q_j|)$

Args:

mat: Ising or QUBO matrix

Returns:

float: Dynamic range

Examples:

>>> import numpy as np
>>> mat = np.array([[0, 8, 1 ,1],
...                 [0, 0, 2, -1],
...                 [0, 0, 0, -8],
...                 [0, 0, 0, 0]])
>>> import kaiwu as kw
>>> kw.preprocess.get_dynamic_range_metric(mat)
np.float64(4.0)

kaiwu.preprocess.get_min_diff(mat)

Calculate the minimum difference

Args:

mat: Ising or QUBO matrix

Returns:

float: Minimum difference

Examples:

>>> import numpy as np
>>> mat = np.array([[0, 8, 1 ,1],
...                 [0, 0, 2, -1],
...                 [0, 0, 0, -8],
...                 [0, 0, 0, 0]])
>>> import kaiwu as kw
>>> kw.preprocess.get_min_diff(mat)
np.int64(1)

kaiwu.preprocess.lower_bound_parameters(ising_mat)

Determine the lower bound of the Ising model Hamiltonian by negating the sum of the absolute values of all coefficients

Args:

ising_mat (np.ndarray): Ising matrix

Returns:

float: Lower bound of the Hamiltonian

Examples:

>>> import numpy as np
>>> import kaiwu as kw
>>> mat = np.array([[0, 18, -12],
...                 [18, 0, 1],
...                 [-12, 1, 0]])
>>> lb = kw.preprocess.lower_bound_parameters(mat)
>>> lb
np.int64(-62)

kaiwu.preprocess.upper_bound_sample(ising_matrix, steps=10)

Estimate the upper bound of the Hamiltonian based on sampling

Args:

ising_matrix (np.ndarray): Ising matrix

steps (int): Number of steps

Returns:

float: Upper bound of the Hamiltonian

Examples:

>>> import numpy as np
>>> import kaiwu as kw
>>> mat = np.array([[0, 18, -12],
...                 [18, 0, 1],
...                 [-12, 1, 0]])
>>> ub = kw.preprocess.upper_bound_sample(mat)

kaiwu.preprocess.upper_bound_simulated_annealing(ising_matrix)

Estimate the upper bound of the Hamiltonian based on simulated annealing

Args:

ising_matrix (np.ndarray): Ising matrix

Returns:

float: Upper bound of the Hamiltonian

Examples:

>>> import numpy as np
>>> import kaiwu as kw
>>> mat = np.array([[0, 18, -12],
...                 [18, 0, 1],
...                 [-12, 1, 0]])
>>> ub = kw.preprocess.upper_bound_simulated_annealing(mat)

kaiwu.preprocess.perform_precision_adaption_mutate(ising_matrix, iterations=100, heuristic='greedy', decision='heuristic')

Iteratively reduce the dynamic range of the Ising matrix by changing one coefficient at a time while keeping the optimal solution unchanged. The idea is referenced from Mücke et al. (2023). This method will change the matrix coefficient values but does not guarantee precision reduction. It can be used for exploratory attempts.

Args:

ising_matrix (np.ndarray): Ising matrix

iterations (int, optional): Number of iterations, default is 100

heuristic (str, optional): Heuristic method for determining the coefficient change amount, including ‘greedy’ and ‘order’. Default is ‘greedy’

decision (str, optional): Method for determining the next modification position. Includes ‘random’ and ‘heuristic’. ‘heuristic’ prioritizes variables that directly affect the dynamic range. Default is ‘heuristic’.

Returns:

np.ndarray: Ising matrix with compressed parameters

Examples:

>>> import numpy as np
>>> mat0 = np.array([[0., -10., 0., 20., 0.55],
...    [-10., 0.,  6120., 0.5, 60.],
...    [0.,  6120., 0.,   0., -5120.],
...    [20.,  0.5,  0.,   0., 1.025],
...    [0.55, 60., -5120., 1.025, 0.]])
>>> import kaiwu as kw
>>> kw.preprocess.perform_precision_adaption_mutate(mat0) 
array([[ 0.  , -2.05,  0.  , 40.  ,  0.  ],
       [-2.05,  0.  ,  4.1 ,  0.  ,  0.  ],
       [ 0.  ,  4.1 ,  0.  ,  0.  , -2.05],
       [40.  ,  0.  ,  0.  ,  0.  ,  2.05],
       [ 0.  ,  0.  , -2.05,  2.05,  0.  ]])

kaiwu.preprocess.perform_precision_adaption_split(ising_matrix: ndarray, param_bit=8, min_increment=None, penalty=None, round_to_increment=True)

Split variables to reduce the coefficient range of the QUBO expression, enabling expression with the required number of bits

Args:

ising_matrix (np.ndarray): Ising matrix

param_bit (int): Number of bits available for Ising matrix elements, representing the parameter precision of the matrix. Default is 8

min_increment (float): Minimum change amount of matrix elements, representing the resolution of the converted matrix. The default value is the smallest positive difference between matrix elements

penalty (float): Penalty term coefficient, default is min_increment * (2^(param_bit-1) - 1)

round_to_increment (bool): Convert all elements of the matrix to integer multiples of min_increment, enabling expression with no more than param_bit bits

Returns:

tuple: Return tuple containing the new matrix and variable indices

• np.ndarray: New matrix with reduced range. Individual elements of the new matrix are not necessarily within the precision range, but the entire matrix will be within the precision range after division by min_increment

• np.ndarray: The first occurrence position of each variable after variable splitting

Examples:

>>> import numpy as np
>>> import kaiwu as kw
>>> mat = np.array([[0, 18, -12],
...                 [18, 0, 1],
...                 [-12, 1, 0]])
>>> kw.preprocess.perform_precision_adaption_split(mat, param_bit=5, min_increment=1, penalty=4,
...        round_to_increment=True)
(array([[ 0.,  4.,  3.,  5., -6.],
       [ 4.,  0.,  5.,  5., -6.],
       [ 3.,  5.,  0.,  4.,  0.],
       [ 5.,  5.,  4.,  0.,  1.],
       [-6., -6.,  0.,  1.,  0.]]), array([1, 3, 4]))

kaiwu.preprocess.restore_split_solution(solution, last_var_idx)

Convert the solution of the reduced-range polynomial back to the solution of the original expression

Args:

solution(np.ndarray): Obtained solution

last_var_idx(np.ndarray): The last occurrence position of each variable after variable splitting

Returns:

np.ndarray: Solution of the original polynomial

Examples:

>>> import kaiwu as kw
>>> import numpy as np
>>> mat = np.array([[0, -15, 0, 30],
...                [-15, 0, 0, 2],
...                [0, 0, 0, 0],
...                [30, 2, 0, 0]])
>>> r, f = kw.preprocess.perform_precision_adaption_split(mat, 5, min_increment=0.5, round_to_increment=True)
>>> worker = kw.classical.SimulatedAnnealingOptimizer()
>>> opt = worker.solve(r)
>>> sol = opt[0] * opt[0, -1]
>>> kw.preprocess.restore_split_solution(sol, f)  
array([ 1, -1, -1,  1], dtype=int8)

kaiwu.preprocess.construct_split_solution(solution, last_var_idx)

After splitting variables of the original matrix to reduce parameter precision, construct the solution of the new matrix based on the solution of the original matrix

Args:

solution (np.ndarray): Solution of the original matrix

last_var_idx (np.ndarray): The last occurrence position of each variable after variable splitting

Returns:

np.ndarray: Solution of the new matrix

Examples:

>>> import numpy as np
>>> import kaiwu as kw
>>> mat = np.array([[0, -15, 0, 40],
...                 [-15, 0, 0, 2],
...                 [0, 0, 0, 0],
...                 [40, 2, 0, 0]])
>>> nmat, tail = kw.preprocess.perform_precision_adaption_split(mat, 5, min_increment=0.5,
...                                                             round_to_increment=True,
...                                                             penalty=0)
>>> sol = np.array([1, 1, -1, -1])
>>> ans = np.array([1, 1, 1, 1, -1, -1, -1, -1])
>>> kw.preprocess.construct_split_solution(sol, tail)
array([ 1.,  1.,  1.,  1., -1., -1., -1., -1.])