高阶问题求解#

1. 高阶优化#

QUBO（Quadratic Unconstrained Binary Optimization）二次无约束二元优化的目的是求得一组布尔变量的值 (x_0,x_1…x_n) ， 使得二阶多项式 x^T Qx 的值最小。

而HOBO（Higher Order Binary Optimization）高阶二元优化可以通过添加约束条件转化为QUBO问题，具体来说，即通过变量替换，令 y=x_0 x_1 ， 将原式中的单项式阶数降低，并添加 y=x_0 x_1 的约束。

而要使得约束成立的方式是在原式中添加惩罚项，即Rosenberg二次惩罚项， p(x_0,x_1,y)=x_0 x_1-2x_0 y-2x_1 y+3y 。 该惩罚项满足 y=x_0x_1 \to p(x_0, x_1,y)=0, y\neq x_0 x_1 \to p(x_0, x_1, y) > 0

最终新的多项式为 f(x,y)+k \sum p(x_i,x_j,y_{ij}) ，其中k是惩罚项系数

2. 注意事项#

新变量为原变量名字用下划线相连，如x0和x1被替换为b_x0_x1，b_x0_x1和b_x0_y1被替换为b_x0_x1_y1

b_是内部保留符号, 不对用户开放用于命名变量.

3. 使用举例#

(1) 降阶#

import numpy as np
import kaiwu as kw

x = kw.core.ndarray(10, "x", kw.core.Binary)
y1 = x[0]*x[1] + x[2]*x[3] + x[8]
y2 = x[3]*x[4] + x[5]*x[6] + x[7]
y3 = y1 * y2
print(y3, "\n")
hobo_model = kw.hobo.HoboModel(y3)
qubo_model = hobo_model.reduce()
print(qubo_model)

执行以上代码后结果为

x[2]*x[3]*x[5]*x[6]+x[2]*x[3]*x[3]*x[4]+x[2]*x[3]*x[7]+x[0]*x[1]*x[5]*x[6]+x[0]*x[1]*x[3]*x[4]+x[0]*x[1]*x[7]+x[5]*x[6]*x[8]+x[3]*x[4]*x[8]+x[7]*x[8]

QUBO Details:
  Variables(Binary):b_x[2]_x[3], b_x[5]_x[6], b_x[0]_x[1], b_x[3]_x[4], x[4], x[7], x[8]
  QUBO offset:      0
  QUBO coefficients:
    b_x[2]_x[3], b_x[5]_x[6] : 1
    b_x[2]_x[3], x[4]        : 1
    b_x[2]_x[3], x[7]        : 1
    b_x[0]_x[1], b_x[5]_x[6] : 1
    b_x[0]_x[1], b_x[3]_x[4] : 1
    b_x[0]_x[1], x[7]        : 1
    b_x[5]_x[6], x[8]        : 1
    b_x[3]_x[4], x[8]        : 1
    x[7], x[8]               : 1
  HOBO Constraint:
    b_x[5]_x[6] : x[5], x[6]
    b_x[2]_x[3] : x[2], x[3]
    b_x[0]_x[1] : x[0], x[1]
    b_x[3]_x[4] : x[3], x[4]

(2) 检查求得的结果是否满足降阶约束条件#

x1, x2, x3 = kw.core.Binary("x1"), kw.core.Binary("x2"), kw.core.Binary("x3")
p = x1*x2*x3
hobo_model = kw.hobo.HoboModel(p)
qubo_model = hobo_model.reduce()
solution = {"x1": 1, "x2": 1, "x3": 0, "b_x1_x2": 1}
err_cnt, _ = hobo_model.verify_constraint(solution)
print(err_cnt)  # 输出0，证明解满足降阶的约束
On this page