kaiwu.preprocess package#

Module contents#

Module: preprocess

Function: Preprocessing related functions

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.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.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.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 package

Contents

kaiwu.preprocess package#

Module contents#