kaiwu.preprocess package#

Module contents#

Module: preprocess

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

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