kaiwu.preprocess package#

Module contents#

模块: preprocess

功能: 预处理相关功能，目前主要是针对ising矩阵的精度相关函数

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

校验QUBO矩阵元素位宽

将QUBO矩阵转为伊辛矩阵，通过校验伊辛矩阵的元素位宽来实现对QUBO矩阵的校验

参数:

qubo_matrix (np.ndarray) -- QUBO矩阵
bit_width (int) -- 位宽

返回:

符合精度要求的 ising 矩阵

返回类型:

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

Examples2（缩放后符合要求）:

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

Examples3(缩放后也不符合要求):

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

调整矩阵精度, 通过此接口调整后矩阵可能会有较大的精度损失，比如矩阵有一个数远大于其它数时，调整后矩阵精度损失严重无法使用

参数:

qubo_matrix (np.ndarray) -- 目标矩阵
bit_width (int) -- 精度范围，目前只支持8位，有一位是符号位

返回:

符合精度要求的QUBO矩阵

返回类型:

np.ndarray

示例

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

计算 ising 矩阵的参数位宽

参数:

ising_matrix (np.ndarray) -- ising 矩阵
bit_width (int) -- 最大位宽限制

返回:

返回Ising矩阵的精度和缩放因子

precision (int): Ising矩阵精度

multiplier (float): 缩放因子

返回类型:

dict

示例

示例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)}

示例2（缩放后符合要求）:

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

示例3(缩放后也不符合要求):

>>> 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 矩阵精度, 通过此接口调整后矩阵可能会有较大的精度损失，比如矩阵有一个数远大于其它数时，调整后矩阵精度损失严重无法使用

参数:

ising_matrix (np.ndarray) -- 目标矩阵
bit_width (int) -- 精度范围，目前只支持8位，有一位是符号位

返回:

符合精度要求的 ising 矩阵

返回类型:

np.ndarray

示例

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

基类：IsingSolver, QuboSolver

降低精度装饰类

通过精度归约和矩阵分裂技术，将大规模或高精度Ising矩阵转换为可在有限比特精度SPQC设备上求解的形式。先截断后split，如果split后精度仍不满足要求则直接截断至目标精度。

适用场景:

矩阵系数精度过高（如含小数1.23或大数10000.0）超出设备表示范围
矩阵规模过大，需要进行split降维

可打开日志看到详细输出: kw.common.set_log_level("DEBUG")

参数:

component (IsingSolver) -- 基础求解器，如SimulatedAnnealingOptimizer
precision (int) -- 矩阵目标精度（小数位数），控制矩阵分裂后的精度
target_bits (int) -- 矩阵目标比特数，默认为None不进行控制
only_feasible_solution (bool) -- 是否只要可行解，默认为False。当only_feasible_solution=True且所有解都不是可行解时会抛出异常KaiwuError
truncated_precision (int) -- 截断精度，与 precision 的差值越大，矩阵分裂后新增的变量数越多。

示例

Example1 (基本用法: 降低矩阵精度):

>>> 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 (处理高精度/大系数矩阵):

>>> 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 (控制目标比特数):

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

get_hamiltonian()#

返回:: 当前解的哈密顿量值
返回类型:: hamiltonian (np.ndarray)

on_matrix_change()#: 更新矩阵相关信息, 继承IsingSolver时可以实现。当处理的ising矩阵发生变化时，这个函数的实现会被调用，从而有机会做相应动作

set_matrix(ising_matrix)#: 设置矩阵并更新相关内容

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

求解Ising矩阵

参数:

ising_matrix (np.ndarray) -- Ising矩阵
negtail_flip (bool) -- 是否进行负尾翻转
sort_solutions (bool) -- 是否对解进行排序

返回:

解向量

返回类型:

output (np.ndarray)

solve_qubo(*args, **kwargs)#

kaiwu.preprocess.get_dynamic_range_metric(mat)#

计算动态范围值（dynamic range, DR）

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

参数:: mat -- Ising或QUBO矩阵
返回:: 动态范围
返回类型:: float

示例

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

计算最小差值

参数:: mat -- Ising或QUBO矩阵
返回:: 最小差值
返回类型:: float

示例

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

所有系数绝对值的和取负，确定Ising模型哈密顿量的下界

参数:: ising_mat (np.ndarray) -- Ising矩阵
返回:: 哈密顿量的下界
返回类型:: float

示例

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

基于采样估计哈密顿量的上界

参数:

ising_matrix (np.ndarray) -- Ising矩阵
steps (int) -- 步数

返回:

哈密顿量的上界

返回类型:

float

示例

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

基于模拟退火估计哈密顿量的上界

参数:: ising_matrix (np.ndarray) -- Ising矩阵
返回:: 哈密顿量的上界
返回类型:: float

示例

>>> 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')#

迭代减小Ising矩阵的动态范围，每次改变一个系数，保持最优解不变。思路参考 Mücke et al. (2023). 此方法会改变矩阵系数数值，但不保证一定能降低精度。可做探索性尝试

参数:

ising_matrix (np.ndarray) -- Ising矩阵
iterations (int, optional) -- 迭代次数，默认为100
heuristic (str, optional) -- 确定系数变化量的启发式方法，包括'greedy'和'order'。默认为'greedy'
decision (str, optional) -- 决定下一个修改位置的方法。包括'random'和'heuristic'。'heuristic'会优先选择直接影响动态范围的变量。默认为'heuristic'。

返回:

压缩参数的Ising矩阵

返回类型:

np.ndarray

示例

>>> 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')#

将变量拆分, 使得QUBO表达式的系数范围缩小, 能够使用要求的比特数表达

参数:

ising_matrix (np.ndarray) -- Ising矩阵
param_bit (int) -- Ising矩阵元素可以使用的比特数，表示矩阵的参数精度。默认为8
min_increment (float) -- 矩阵元素的最小变化量，表示转化后矩阵的分辨率。默认值取矩阵元素间差值的最小正值
penalty (float) -- 惩罚项系数，默认为min_increment * (2^(param_bit-1) - 1)
round_to_increment (bool) -- 将矩阵的所有元素转化为min_increment的整数倍，使得其可以用不超过param_bit的比特数表达
method (str) -- 拆分方法，包括 "var" 和 "item"，默认为 "var"。

返回:

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

np.ndarray: 包含缩小范围的新矩阵。新矩阵单个元素并不一定在精度范围内，但是整体除以min_increment后会在精度范围内
np.ndarray: 原变量在新矩阵中的代表索引

返回类型:

tuple

示例

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

将缩小范围多项式的解转换回原来的表达式的解

参数:

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

返回:

原多项式的解

返回类型:

np.ndarray

示例

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

将原矩阵分拆变量降低参数精度后，根据原矩阵的解构造新矩阵的解

参数:

solution (np.ndarray) -- 原矩阵的解
last_var_idx (np.ndarray) -- 分拆后每个变量最后一次出现的位置

返回:

新矩阵的解

返回类型:

np.ndarray

示例

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