Cubic Optimization

Source: examples/cubic_opt/README.md

Minimise a cubic pseudo-Boolean objective over binary variables via single-stage HOBO degree reduction.

QUBO formulation

• Input: N binary variables, M cubic interaction terms (i, j, k, c)
• Model: N binary variables. Linear bias -1 per variable rewards selection, creating tension with the positive cubic terms.
• Objective: sum(c_t * x_i * x_j * x_k) - sum(x_v)

Each cubic term (i, j, k, c) is degree-reduced to quadratic via:

1. REDUCE(i, j, P_AUX) -> w – allocates auxiliary variable w with Rosenberg enforcement P_AUX*(x_i*x_j - 2*x_i*w - 2*x_j*w + 3*w)
2. ADDQUAD(w, k, c) – adds c*w*x_k = c*x_i*x_j*x_k to the QUBO

DSL methods used

• model.reduce(var_a, var_b, p_aux) – single-stage HOBO degree reduction

Pipeline overview

1. CP (xqcp) – generate random cubic interaction terms, declare binary variables with linear bias, and degree-reduce each cubic term via REDUCE.
2. Assemble – .xqasm text to bytecode via xquad.asm
3. Encode – run encoder on chosen XQVM to produce the XQMX model
4. Sample – solver runs SA/QPU/GPU over the model
5. Verify – verifier checks constraints and computes energy
6. Decode – decoder extracts the variable assignment

Usage

uv run python examples/cubic_opt/runner.py --seed 42
uv run python examples/cubic_opt/runner.py --n 5 --m 4 --interpreter rust

Choosing a solver

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.