HOBO#

1. High Order Binary Optimization#

Quadratic unconstrained binary optimization is aimed at obtaining the values of a set of Boolean variables $(x_0,x_1…x_n)$ ， to minimize $x^T Qx$

Higher-order binary optimization can be translated into a QUBO problem by adding constraints. Specifically, by variable substitution, such as $y= x_0x_1$ , reduces the monomial order in the original expression and adds the constraint $y= x_0x_1$ .

And the way to make the constraint work is to add a penalty term to the original formula, the Rosenberg secondary penalty term. $p(x_0,x_1,y)=x_0 x_1-2x_0 y-2x_1 y+3y$ The penaly term satisfies $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$

The new polynomial is $f(x,y)+k \sum p(x_i,x_j,y_{ij})$ , k is penalty coefficient

2. Matters need attention#

The new variable is the name of the original variable with an underscore, for example, x0 and x1 are replaced with _x0_x1, and _x0_x1 and _x0_y1 are replaced with _x0_x1_y1

_ is an internal reserved symbol and is not available to users for naming variables.

3. Examples#

(1) Reduce degree after modeling#

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)

The result executing the above code is

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] is a new variable after the _x[5] and _x[6] variables are merged

(2) Reduce degree in calculation#

# 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)

The result after the reduction is

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) Check whether the obtained results meet the reduced order constraints#

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)

The result is 0, which proves that the solution satisfies the reduced order constraint

HOBO

Contents