QAOA: Quantum Approximate Optimization

QAOA is the leading gate-model approach to combinatorial optimization; Kronos evaluates it for scheduling and layout, with no advantage assumed.

Optimization as an energy minimum

Many Kronos planning problems, fleet maintenance windows, experiment campaign order, component layout, are combinatorial optimizations. The quantum approximate optimization algorithm (QAOA) encodes the objective as an Ising Hamiltonian whose ground state is the optimal assignment, then alternates two operators to push a state toward it.

# Encode cost C(z) over bit strings z as a diagonal Hamiltonian:
H_C |z> = C(z) |z>          # e.g. Ising:  C = sum J_ij z_i z_j + sum h_i z_i
H_B = sum_i X_i             # mixer (transverse field)

# QAOA depth-p ansatz:
|gamma,beta> = prod_{l=1..p} [ exp(-i beta_l H_B) exp(-i gamma_l H_C) ] |+>^n
# classically optimize (gamma,beta) to minimize <H_C>

How it is meant to work

• The cost-operator phase separation marks good bit strings; the mixer spreads amplitude toward them.
• Depth p controls expressivity: p -> infinity recovers the adiabatic optimum, but depth is limited by noise.
• A classical optimizer tunes the 2p angles using measured expectation values.

The honest verdict

QAOA has no proven advantage over classical heuristics for the problem sizes and depths reachable on current hardware. At shallow depth it is often matched or beaten by classical solvers like simulated annealing and specialized branch-and-bound. Kronos treats it as a candidate to be benchmarked, never as a default. See the concrete mappings for maintenance scheduling and campaign scheduling, the required QUBO/Ising encodings, and the annealing comparison.

Crucially, none of this runs in operations. Scheduling for the real machines is done by classical solvers with hard safety constraints; QAOA is an L0 research track that must first beat the classical baseline on Kronos-shaped instances before it earns any production role.