PUBO

PUBO / HUBO

Higher-order unconstrained binary optimization — degree 3 and beyond.

In plain terms

Sometimes the switches don’t just interact in pairs — three or more of them combine at once to drive the cost. Quantum machines and ordinary QUBO solvers have to break those group effects apart into pairs first, which bloats the problem. Quicopt keeps the original group interactions and solves them as they are.

The technical picture

PUBO (polynomial) and HUBO (higher-order) generalize QUBO: binary variables with a polynomial objective of degree ≥ 3, no constraints. Many real binary problems are naturally higher-order — only QUBO solvers force them down to degree two.

A QPU, or any QUBO solver, must reduce higher-order terms to quadratic by adding auxiliary variables and penalty terms, which inflates the problem and distorts its landscape. Quicopt optimizes the original higher-order objective directly — no reduction.

Mathematical model▾

Minimize a polynomial of degree ≥ 3 over binary variables (PUBO); arbitrary order is HUBO. Equivalently, a higher-order Ising energy over spins.

x \in {0, 1}^{n} min i \sum a_{i} x_{i} + i < j \sum b_{ij} x_{i} x_{j} + i < j < k \sum c_{ij k} x_{i} x_{j} x_{k} + \dots

degree \geq 3 is PUBO; arbitrary order is HUBO.

Example

From install to solved model — a small, self-contained example, copy-paste ready.

Install the client

$ pip install "quicopt[pyomo]"

Copy the example

pubo.py

import pyomo.environ as pyo
from quicopt import Client

# A PUBO: the LABS problem (low-autocorrelation binary sequences) for N=7.
# Spins s_i = 1 - 2 x_i turn the binary x into +/-1; the energy
# sum_k C_k^2 with C_k = sum_i s_i s_{i+k} is a degree-4 polynomial.
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)

client = Client("https://try.quicoptapi.pgi.fz-juelich.de")
result = client.solve(m)
print(result.display)

Run it

$ python pubo.py

What you’ll see

├── status:     heuristic
├── feasible:   true
├── objective:  3.0
├── x:          x1=0, x2=0, x3=0, x4=1, x5=1, x6=0, …  (7 variables)
└── solve_time: 3.5084 s

Docs, API reference and more examples live in the Developer Hub →

Benchmark

LABS (QOBLIB) is a hard higher-order binary problem whose natural objective is a degree-four polynomial — see the measured comparison against Gurobi and ABS2.

LABS — Low-Autocorrelation Binary Sequences