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

Parameters:

qubo_matrix (np.ndarray) – QUBOmatrix
bit_width (int) – bit width

Returns:

np.ndarray: Ising matrix that satisfies the precision requirements

Return type:

np.ndarray

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

Parameters:

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

Return type:

np.ndarray

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

Parameters:

ising_matrix (np.ndarray) – ising matrix
bit_width (int) – maximum bit-width limit

Returns:

Returns the precision and scaling factor of the Ising matrix - precision (int): Ising matrix precision - multiplier (float): Scaling factor

Return type:

dict

Examples

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

Parameters:

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

Return type:

np.ndarray

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

Applicable scenarios: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”)

Parameters:

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) – Example 3 (Control target number of bits):
truncated_precision (int) – truncation precision. The larger the difference from precision, the more variables are added after matrix splitting.

Examples

Example 1 (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)

Example 2 (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)

Example 3 (Control target number of bits):

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

get_hamiltonian()#

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

on_matrix_change()#: Dynamic rangeUpdate 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

Parameters:

ising_matrix (np.ndarray) – Ising matrix
negtail_flip (bool) – Whether to perform negative-tail flipping
sort_solutions (bool) – Whether to sort solutions

Returns:

solution vector

Return type:

output (np.ndarray)

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|)$

Parameters:: mat – mat: Ising or QUBO matrix
Returns:: Dynamic range
Return type:: float

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

Parameters:: mat – mat: Ising or QUBO matrix
Returns:: Calculate the minimum difference
Return type:: float

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

Parameters:: ising_mat (np.ndarray) – Ising matrix
Returns:: Lower bound of the Hamiltonian
Return type:: float

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

Parameters:

ising_matrix (np.ndarray) – Ising matrix
steps (int) – Number of steps

Returns:

Estimate the upper bound of the Hamiltonian based on sampling

Return type:

float

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

Parameters:: ising_matrix (np.ndarray) – Ising matrix
Returns:: Estimate the upper bound of the Hamiltonian based on sampling
Return type:: float

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) <http://arxiv.org/abs/2307.02195>_. This method will change the matrix coefficient values but does not guarantee precision reduction. It can be used for exploratory attempts.

Parameters:

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:

Solve the Ising matrix

Return type:

np.ndarray

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, method='var')#

Solution of the original polynomialSplit variables to reduce the coefficient range of the QUBO expression, enabling expression with the required number of bits

Parameters:

ising_matrix (np.ndarray) – Ising matrix
param_bit (int) – Solution of the new matrixNumber 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
method (str) – 拆分方法，包括 "var" 和 "item"，默认为 "var"。

Returns:

返回元组，包含新矩阵和原变量索引

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: 原变量在新矩阵中的代表索引

Return type:

tuple

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, split_indices)#

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

Parameters:

solution (np.ndarray) – Obtained solution
split_indices (np.ndarray) – 原变量在拆分后矩阵中的代表索引。对于变量拆分，该索引为每个原变量最后一个副本的位置；对于项拆分，原变量保留在矩阵前部，因此该索引为 [0, 1, ..., n - 1]。

Returns:

Solution to the original polynomial

Return type:

np.ndarray

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=None)#

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 matrixAfter 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

Parameters:

solution (np.ndarray) – Solution of the original matrix
last_var_idx (np.ndarray) – The last occurrence position of each variable after variable splitting

Returns:

Solution to the new matrix

Return type:

np.ndarray

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.])