参数精度#

参数精度转化要求#

在对实际问题进行建模时，常常得到QUBO形式，再将其转化成Ising模型就可以应用于物理机了。QUBO模型需要转化为 Ising模型 \mathcal{H}=-\sum_{i,j}J_{ij}s_is_j-\mu\sum_ih_is_i 以用于实际的物理计算

实际计算中，系数位宽受到物理上硬件条件的限制，只能取有限的范围。

1.CIM真机只支持8bit INT空间[-128, 127]

2.用户建模要保证转换完的Ising矩阵符合要求

3.提供的转换逻辑供参考，用户可以根据自己的矩阵使用更适合的方法

QUBO转化为Ising#

本节介绍QUBO如何转化为Ising，以便于理解动态范围检查如何限制QUBO矩阵。

QUBO模型如下：

\mathcal{H}= \sum_{i}{q_{ii}x_{i}} +\sum_{i\neq j}{q_{ij}x_{i}x_{j}}

在计算之前需要将其转化为Ising矩阵。 令 s_{i} = 2x_{i}-1 \in \{1,-1\},

\mathcal{H} =& \sum_{i}{q_{ii}\cdot \frac{s_{i}+1}{2}} +\sum_{i\neq j}{q_{ij}\cdot \frac{(s_{i}+1)(s_{j}+1)}{4}} \\ = &\sum_{i\neq j} \frac{q_{ij}}{4}s_{i}s_{j} +\sum_{i} \Big(\frac{q_{ii}}{2}+\frac{\sum_{k\neq i}{(q_{ik}+q_{ki})}}{4}\Big) s_{i} + \Big(\frac{\sum_{i} q_{ii}}{2} +\frac{\sum_{i\neq j}q_{ij}}{4}\Big)

QUBO变量满足 x^2 = x，可以用矩阵的对角线元素表达一次项。而Ising模型 x^2 = 1，不能这样表示。

上式中的一次项通过添加辅助变量 s 化为二次项，辅助变量取1和-1时可以分别对应到添加辅助变量前的两组解。故添加辅助变量后与原问题等价。

常数项单独记录，在计算最终哈密顿量时加上即可。

举例：

x^\top\left( \begin{array}{ll} 0 & 2\\ 1 & 1 \end{array}\right)x

经过变换之后为

s^\top\left( \begin{array}{lll} 0 & 3/8 & 3/8\\ 3/8 & 0 & 5/8 \\ 3/8 & 5/8 & 0 \end{array} \right) s+3/2

kaiwuSDK降低精度的方法#

kaiwuSDK提供了两种降低参数精度的方法，perform_precision_adaption_mutate和perform_precision_adaption_split。 mutate方法在修改矩阵的同时能够保持矩阵的解不变，但能够改变精度的程度取决于矩阵本身的可下降空间。 split方法能够将矩阵修改到任意精度，但是新矩阵的比特数随着精度变化量增长较快

perform_precision_adaption_mutate#

1 动态范围#

1.1 QUBO矩阵相关定义

定义 Q为qubo矩阵， Q \subseteq Q' 表示Q的最优解包含于Q'的最优解

定义 \lfloor Q \rceil 为对Q的每个元素round取整

1.2 动态范围相关定义

定义 \hat{D}(X) 为X元素的最大距离

\check{D}(X) 为X元素的最小距离

DR(X):=log_2(\frac{\hat{D}(X)}{\check{D}(X)}) 为X的动态范围

命题 \hat{D}(Q)=1, 那么 \forall \alpha > 0, DR(\lfloor \alpha Q \rceil) \leq log_2(1+\alpha)

通过减小动态范围，可以降低原矩阵所需要的参数精度

2. 应用举例#

import kaiwu as kw
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]])
mutated_mat = kw.preprocess.perform_precision_adaption_mutate(mat0)
print(mutated_mat)

perform_precision_adaption_split#

1. 参数精度#

由于当前量子计算机对QUBO系数的存储方式为定点数，且只有8位精度，对于最大最小值的比值超过 2^8 的多项式，需要将系数大的项分拆。

实现方式为将原式中的比特替换成值相等的多个等价比特，相等条件由约束项实现，从而使得每一项的系数都能够缩小。

以QUBO表达式为例，拆分的方式为将 f(\mathbf{x}) 转化为

f(\mathbf{x}, \mathbf{x'})+M\sum_i (x_i - x_{i1})^2+M\sum_{i,j} (x_{ij}-x_{i(j+1)})^2= \\ f(\mathbf{x}, \mathbf{x'})+M\sum_i (x_i + x_{i1} - 2x_ix_{i1})+M\sum_{i,j} (x_{ij} + x_{i(j+1)} - 2x_{ij}x_{i(j+1)})

例如，对于 x_1+2x_2+200x_3，要求多项式系数最大最小值的比值不能超过150， 阈值设置为那么将多项式修改为 x_1+2x_2+100x_3+100x_{31}+50(x_3-x_{31})^2=x_1+2x_2+100x_3+100x_{31}+50(x_3+x_{31}-2x_3x_{31})

2. 应用举例#

import kaiwu as kw
import numpy as np

mat = np.array([[0, -15,0, 40],
                [-15,0, 0, 1],
                [0,  0, 0, 0],
                [40, 1, 0, 0]])
splitted_ret, last_idx = kw.preprocess.perform_precision_adaption_split(mat, 4)
print(splitted_ret)

min_increment计算得到默认值为1。精度设置为4个比特，范围在-7到7，绝对应该小于7。

程序输出转换后的矩阵如下：

../_images/precision_split.png

如图所示，红色的箭头指示出拆分前后的对应关系。蓝色框中的数字则是用于限制新建的变量的值保持一致的惩罚项。 通过这样拆分变量，可以在保持原矩阵的解的情况下，将参数精度降低。

降低精度的过程通过param_bit，min_increment，penalty, round_to_increment等参数来调节。

矩阵的值都是min_increment的整数倍，默认取矩阵元素间的最小正差值

round_to_increment表示在这个过程中，通过调整各个元素，使得拆分后的元素的和等于原值。 如15拆分成7.5+7.5，若分别近似取整会变成8+8。设置reduce_error=True，15会自动拆分为7+8

splitted_ret2, last_idx2 = kw.preprocess.perform_precision_adaption_split(mat, 4, min_increment=3, round_to_increment=True)
print(splitted_ret2)

结果为

[[ 0. 21. -6.  0.  3. 12.]
[21.  0. -9.  0. 12. 12.]
[-6. -9.  0.  0.  0.  0.]
[ 0.  0.  0.  0.  0.  0.]
[ 3. 12.  0.  0.  0. 21.]
[12. 12.  0.  0. 21.  0.]]

对拆分后精度满足要求的矩阵进行求解后，可以通过restore_splitted_solution将其恢复成原矩阵的解

worker = kw.cim.SimulatedCIMOptimizer(iterations=1000)
output = worker.solve(splitted_ret)
opt = kw.sampler.optimal_sampler(splitted_ret, output, bias=0, negtail_ff=False)
sol = opt[0][0]
org_sol = kw.preprocess.restore_splitted_solution(sol, last_idx)
print(org_sol)

结果为

[-1.  1. -1. -1.]

PrecisionReducer#

为了方便用户在SDK中迭代调用CIM量子计算机，SDK提供了PrecisionReducer， 它应用了装饰模式（一种软件设计模式）。 当用户需要在提交量子计算机求解时，可以在CIMOptimizer之外再讨一个PrecisionReducer，然后把PrecisionReducer作为Optimizer传给Solver。 详情参见

参见

更多的有关精度处理的方法#

参见