Higher-Order Problem Solving#

1. Higher-Order Optimization#

Quadratic Unconstrained Binary Optimization (QUBO) aims to determine a set of Boolean variables $(x_0, x_1, … , x_n)$ that minimize a quadratic polynomial $x^T Q x$ .

Higher-Order Binary Optimization (HOBO) problems can be converted into QUBO problems by introducing constraints. Specifically, a new variable can be introduced such that $y = x_0 x_1$ , thereby reducing the degree of the monomial while adding the constraint enforcing $y = x_0 x_1$ .

To enforce this constraint, a penalty term can be added to the objective function, specifically the Rosenberg quadratic penalty: $p(x_0, x_1, y) = x_0 x_1 - 2 x_0 y - 2 x_1 y + 3y$ . This satisfies: $y = x_0 x_1 \Rightarrow p(x_0, x_1, y) = 0$ , and $y \neq x_0 x_1 \Rightarrow p(x_0, x_1, y) > 0$ .

The resulting polynomial becomes $f(x, y) + k \sum p(x_i, x_j, y_{ij})$ , where $k$ is the penalty coefficient.

2. Usage Example#

(1) Degree Reduction#

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]
y3 = y1 * y2
print(y3, "\n")
hobo_model = kw.hobo.HoboModel(y3)
qubo_model = hobo_model.reduce()
print(hobo_model, "\n")
print(qubo_model)

The result after executing the above code is as follows:

Minimize x[2]*x[3]*x[5]+x[2]*x[3]*x[4]+x[0]*x[1]*x[5]+x[0]*x[1]*x[3]*x[4]+x[5]*x[8]+x[3]*x[4]*x[8]
Subject to (hobo constraints):
_x[2]_x[3] := x[2] * x[3]
_x[0]_x[1] := x[0] * x[1]
_x[3]_x[4] := x[3] * x[4]

Minimize _x[2]_x[3]*x[5]+_x[2]_x[3]*x[4]+_x[0]_x[1]*x[5]+_x[0]_x[1]*_x[3]_x[4]+x[5]*x[8]+_x[3]_x[4]*x[8]
Subject to (hard constraints):
x[2]*x[3]-2*_x[2]_x[3]*x[2]-2*_x[2]_x[3]*x[3]+3*_x[2]_x[3]
x[0]*x[1]-2*_x[0]_x[1]*x[0]-2*_x[0]_x[1]*x[1]+3*_x[0]_x[1]
x[3]*x[4]-2*_x[3]_x[4]*x[3]-2*_x[3]_x[4]*x[4]+3*_x[3]_x[4]

(2) Verify whether the solved result satisfies the degree-reduction constraints#

import kaiwu as kw

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, "_x1_x2": 1}
err_cnt, _ = hobo_model.verify_hobo_constraint(solution)
print(err_cnt)  # 输出0，证明解满足降阶的约束