高阶问题求解#

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被替换为_x0_x1，_x0_x1和_x0_y1被替换为_x0_x1_y1

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

3. 使用举例#

(1) 计算后降阶#

import numpy as np
import kaiwu as kw

kw.qubo.QuboExpression.auto_hobo_reduce = False
x = kw.qubo.ndarray(10, "x", kw.qubo.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")
reducer = kw.qubo.HoboReducer()
y4 = reducer.reduce(y3)
kw.qubo.details(y4)

执行以上代码后结果为

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):_x[0]_x[1], _x[2]_x[3], _x[3]_x[4], _x[5]_x[6], x[4], x[7], x[8]
QUBO offset:      0
QUBO coefficients:
    _x[2]_x[3], _x[5]_x[6] : 1
    _x[2]_x[3], x[4]       : 1
    _x[2]_x[3], x[7]       : 1
    _x[0]_x[1], _x[5]_x[6] : 1
    _x[0]_x[1], _x[3]_x[4] : 1
    _x[0]_x[1], x[7]       : 1
    _x[5]_x[6], x[8]       : 1
    _x[3]_x[4], x[8]       : 1
    x[7], x[8]             : 1
HOBO Constraint:
    _x[5]_x[6] : x[5], x[6]
    _x[2]_x[3] : x[2], x[3]
    _x[0]_x[1] : x[0], x[1]
    _x[3]_x[4] : x[3], x[4]

_x[5]_x[6] 为 _x[5] 和 _x[6] 变量合并后的新变量

(2) 计算时降阶#

# auto_hobo_reduce defaults to True
kw.qubo.QuboExpression.auto_hobo_reduce = True

x1, x2, x3 = kw.qubo.Binary("x1"), kw.qubo.Binary("x2"), kw.qubo.Binary("x3")
y1, y2, y3 = kw.qubo.Binary("y1"), kw.qubo.Binary("y2"), kw.qubo.Binary("y3")
p1 = x1 * x2 + 2* y1 * y1
p2 = x1 * y1 + y3
result = p1 * p2
kw.qubo.details(result)

执行以上代码后得到降阶后的结果为

QUBO Details:
  Variables(Binary):_x1_x2, _x1_y1, y1, y3
  QUBO offset:      0
  QUBO coefficients:
    y1, y3         : 2
    _x1_y1, y1     : 2
    _x1_x2, y3     : 1
    _x1_x2, _x1_y1 : 1
  HOBO Constraint:
    _x1_y1 : x1, y1
    _x1_x2 : x1, x2

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

p = x1*x2*x3
err_cnt, result_dic = kw.qubo.hobo_verify(p, {"x1":1,"x2":1,"x3":0,"_x1_x2":1})
print(err_cnt)

得到结果为0，证明解满足降阶的约束

高阶问题求解

目录