Mapping Fusion Problems to QUBO and Ising

Every quantum optimizer consumes an Ising or QUBO form; getting Kronos constraints into that form correctly is where most of the real work lives.

The common target form

Quantum annealers and QAOA both minimize a quadratic function over binary variables. Quadratic unconstrained binary optimization (QUBO) uses bits x in {0,1}; the Ising form uses spins z in {-1,+1}. They are equivalent under x = (1 - z)/2. Casting a Kronos planning problem into this form is the modeling step that determines whether a quantum solver can even represent it.

QUBO:   minimize  x^T Q x ,     x_i in {0,1}
Ising:  minimize  sum_i h_i z_i + sum_{i<j} J_ij z_i z_j,  z in {-1,+1}
map:    x_i = (1 - z_i)/2
# only linear and quadratic terms allowed -> higher-order terms must
# be reduced with auxiliary variables (quadratization)

Turning constraints into penalties

QUBO is unconstrained, so every hard constraint becomes a squared penalty added to the objective with a weight large enough that any violation costs more than any objective gain.

constraint  sum_i a_i x_i = b   -->   + P * ( sum_i a_i x_i - b )^2
inequality  sum_i a_i x_i <= b   -->   introduce slack bits s:
                                       + P * ( sum a_i x_i + s - b )^2
# choose P > (max objective range); too large P worsens conditioning

Kronos-specific modeling pitfalls

• Integer quantities (windows, positions) need binary/one-hot encodings that inflate variable count quadratically.
• Higher-order interactions (three-unit availability rules) require quadratization with ancilla bits, growing the graph.
• Annealers add minor-embedding: logical variables map to chains of physical qubits, further multiplying resources.

These overheads are why a problem that looks small can exceed hardware limits once encoded, and why the classical baseline usually wins today. Correct penalty weighting is also a correctness issue: a mis-weighted penalty can make an infeasible schedule look optimal. Kronos validates every encoding by checking that the classical optimum of the QUBO matches the classical optimum of the original constrained problem before any quantum run. Used by maintenance and campaign scheduling.