kaiwu.preprocess package#

Module contents#

Module: preprocess

Function: Preprocessing related functions, currently mainly for precision related functions of ising matrices

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

Calculate the parameter bit width of the ising matrix

Args:

ising_matrix (np.ndarray): ising 矩阵

bit_width (int): Maximum bit width limit

Returns:

Dict: Returns the precision and scaling factor of the Ising matrix

precision (int): Ising矩阵精度

Multiplier (float): scaling factor

Example 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': 1.0}

Example 2 (meets the 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': 10.0}

Example 3 (also does not meet the requirements 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)#

Adjust the accuracy of the ising matrix. After adjusting the matrix through this interface, there may be a large loss of accuracy. For example, when one number of the matrix is much larger than the other numbers, the adjusted matrix accuracy loss is serious and cannot be used.

Args:

ising_matrix(np.ndarray): 目标矩阵

bit_width (int): Precision range, currently only supports 8 bits, one bit is the sign bit

Returns:

np.ndarray: 符合精度要求的 ising 矩阵

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

kaiwu.preprocess.get_dynamic_range_metric(mat)#

Calculate dynamic range (DR)

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

kaiwu.preprocess.lower_bound_parameters(ising_mat)#

The sum of the absolute values of all coefficients is negative, which determines the lower bound of the Ising model Hamiltonian

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

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

Estimating the upper bound of the Hamiltonian based on sampling

Args:

ising_matrix (np.ndarray): Ising matrix

steps (int): 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)#

Estimating 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, changing one coefficient each time to keep the optimal solution unchanged. Mücke et al. (2023).

Args:

ising_matrix (np.ndarray): Ising matrix

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

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

decision (str, optional): The method to determine the next modification position. Includes ‘random’ and ‘heuristic’. ‘heuristic’ will give priority to variables that directly affect the dynamic range. The default is ‘heuristic’.

Returns:

np.ndarray: Ising matrix of compression parameters

Examples:

>>> import numpy as np
>>> mat0 = np.array([[0, -20, 0, 40, 1.1],
...                  [0, 0, 12240, 1, 120],
...                  [0, 0, 0, 0, -10240],
...                  [0, 0, 0, 0, 2.05],
...                  [0, 0, 0, 0, 0]])
>>> import kaiwu as kw
>>> kw.preprocess.perform_precision_adaption_mutate(mat0) 
array([[ 0.  , -2.05,  0.  ,  2.05,  0.  ],
       [ 0.  ,  0.  ,  4.1 ,  0.  ,  0.  ],
       [ 0.  ,  0.  ,  0.  ,  0.  , -2.05],
       [ 0.  ,  0.  ,  0.  ,  0.  ,  2.05],
       [ 0.  ,  0.  ,  0.  ,  0.  ,  0.  ]])

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

Split the variables so that the coefficient range of the QUBO expression is reduced and can be expressed using the required number of bits

Args:

ising_matrix (np.ndarray): Ising matrix

param_bit (int): The number of bits that can be used by the Ising matrix elements, indicating the parameter precision of the matrix. The default value is 8

min_increment (float): The minimum change in matrix elements, indicating the resolution of the transformed matrix. The default value is the minimum positive value of the difference between matrix elements.

penalty (float): penalty 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 so that they can be expressed in no more than param_bit bits.

Returns:

tuple: returns a tuple containing the new matrix and variable indices

np.ndarray: new matrix containing the reduced range
np.ndarray: The first position of the variable after the variable is split

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)
(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_splitted_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): the solution found

last_var_idx(np.ndarray): The last position of each variable after 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()
>>> output = worker.solve(r)
>>> opt = kw.sampler.optimal_sampler(r, output, bias=0, negtail_ff=False)
>>> sol = opt[0][0] * opt[0][0, -1]
>>> kw.preprocess.restore_splitted_solution(sol, f)  
array([ 1, -1, -1,  1], dtype=int8)

kaiwu.preprocess.construct_splitted_solution(solution, last_var_idx)#

After splitting the original matrix into variables to reduce the parameter precision, the solution of the new matrix is constructed based on the solution of the original matrix.

Args:

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

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

Returns:

np.ndarray: solution to 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_splitted_solution(sol, tail)
array([ 1.,  1.,  1.,  1., -1., -1., -1., -1.])

kaiwu.preprocess package

Contents

kaiwu.preprocess package#

Module contents#