Problem class. Decision variables are encoded as bitstrings x ∈ {0,1}ⁿ with objective f(x) and constraints gᵢ(x) ≤ 0. Objectives are typically reformulated as QUBO / Ising Hamiltonians — the native input for annealers and gate-model variational algorithms such as QAOA.
Why NISQ alone is insufficient. Gate and measurement noise, finite shots, and local bit-flip corruption mean raw quantum samples are biased but imperfect proposals. Classical greedy correction recovers much of the lost solution quality at O(n) cost.
QAOA. Alternating cost and mixing unitaries for p rounds with classically tunable angles produce a distribution biased toward lower-cost regions; usable NISQ depths remain shallow.
Classical refinement. A push-forward mapping r concentrates probability mass into better local minima via bit-flip local search, configuration-recovery repair, and optional diversity-preserving post-processing.
Formal verification. SMT solvers (e.g. Z3) certify hard constraints post hoc or guide constrained search — converting "looked good in testing" into machine-checkable feasibility.
