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. Important Notes#

New variables are formed by joining the original variable names with underscores. For example, $x0$ and $x1$ are replaced by b_x0_x1, and b_x0_x1 and b_x0_y1 are then replaced by b_x0_x1_y1.

The prefix `b_` is reserved internally and cannot be used for user-defined variable names.

3. Usage Example#

(1) Degree Reduction#

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)

The result after executing the above code is as follows:

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) Verify whether the solved result satisfies the degree-reduction constraints#

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，证明解满足降阶的约束