Higher-order binary optimization (PUBO) in Python

Not every binary problem is quadratic. When the objective multiplies three or more binary variables together, it is a PUBO (polynomial) or HUBO (higher-order) problem — the class quantum computers are built for, here solved classically. quicopt optimizes the higher-order objective directly: no reduction to a quadratic QUBO, no auxiliary variables.

The naive approach

The common workaround is to reduce the degree — introduce a helper binary for each product of variables until everything is quadratic, then feed a QUBO solver. That inflates the variable count and adds penalty terms that reshape the energy landscape. Solve the objective as written instead.

A worked example: LABS

The low-autocorrelation binary sequence (LABS) problem asks for a string of ±1 symbols that looks as little like a shifted copy of itself as possible. Its energy is a degree-four polynomial in the binaries — a genuine PUBO. Modeled in Pyomo (pip install "quicopt[pyomo]"), here for N = 7:

import pyomo.environ as pyo
from quicopt import Client
# LABS (low-autocorrelation binary sequences) for N=7: a degree-4 (PUBO) energy.
N = 7
m = pyo.ConcreteModel()
m.x = pyo.Var(range(N), domain=pyo.Binary)
s = [1 - 2 * m.x[i] for i in range(N)]
m.obj = pyo.Objective(
    expr=sum(sum(s[i] * s[i + k] for i in range(N - k)) ** 2 for k in range(1, N)),
    sense=pyo.minimize)
print(Client("https://try.quicoptapi.pgi.fz-juelich.de").solve(m).display)

├── shots
│   ├── 1 · Heuristic 1   91    0.0s
│   ├── 2 · Heuristic 2    3   0.01s  ◀ best
│   └── 3 · Heuristic 3    3   3.58s
├── status:     heuristic
├── feasible:   n/a
├── objective:  3.0
├── x:          x1=1, x2=0, x3=1, x4=1, x5=0, x6=0, …  (7 variables)
└── solve_time: 3.5866 s

What you get

quicopt returns energy 3 — the known optimum for LABS at N = 7 (established by exhaustive results in the literature) — straight from the degree-four objective, with no manual reduction to quadratic. Because a PUBO has no constraints, the status is heuristic, and the few seconds reflect several heuristic passes over the non-convex energy — inherent to higher-order search, not a fixed overhead.

The same directness scales: on the public LABS instances quicopt reaches best-known energies orders of magnitude faster than established solvers — see the LABS benchmark.

Next

• The problem class behind this: PUBO / higher-order binary
• Measured results at scale: LABS benchmark
• The quadratic cousin: Max-cut (QUBO)

Reference: T. Packebusch and S. Mertens, Low autocorrelation binary sequences, Journal of Physics A, 2016.