Case Study: Encoding a Real Constraint Problem — and the Penalty Tax

Executive Summary

QAOA benchmarks use MaxCut because MaxCut maps onto qubits with no effort: one qubit per node, one $ZZ$ term per edge, no constraints. Real optimization problems are not like that. They have equality constraints, integer variables, and inequalities, and every one of them must be forced into an unconstrained Ising Hamiltonian before QAOA can touch it.

This case study encodes a nurse-scheduling problem end to end and tracks what the encoding costs: qubit count, Hamiltonian density, penalty-weight tuning, and the fraction of the search space that becomes infeasible garbage. The overhead dwarfs the algorithm.

Skills applied

• Converting constrained optimization to QUBO/Ising form (§20.12).
• Encoding equality and inequality constraints with penalty terms.
• Analyzing feasible-fraction collapse and its consequences for sampling.
• Assessing encoding overhead against the algorithm's cost.

Phase 1: The problem

Assign 12 nurses to 21 shifts (7 days × 3 shifts) subject to:

1. Coverage: each shift needs exactly 3 nurses.
2. Rest: no nurse works consecutive shifts.
3. Fairness: each nurse works 5–6 shifts per week.
4. Preferences: maximize satisfied shift preferences.

Natural variables: $x_{ns} \in \{0,1\}$ for nurse $n$ on shift $s$ → $12 \times 21 = 252$ binary variables → 252 qubits.

Already, before any algorithm, this problem needs more qubits than most devices have and more than the largest QAOA demonstration by an order of magnitude.

Phase 2: Penalty encoding

QAOA optimizes an unconstrained Ising Hamiltonian, so constraints become penalty terms whose violation costs energy.

Coverage (equality constraint). For each shift $s$:

$$H_{\text{cov}} = A\sum_{s}\left(\sum_n x_{ns} - 3\right)^2$$

Expanding the square produces all pairwise products $x_{ns}x_{n's}$ — that is $\binom{12}{2} = 66$ quadratic terms per shift, times 21 shifts = 1,386 terms from this constraint alone.

Rest (implication constraint). For each nurse and consecutive shift pair:

$$H_{\text{rest}} = B\sum_{n}\sum_{s} x_{ns}x_{n,s+1}$$

12 × 20 = 240 terms.

Fairness (inequality constraint). Inequalities need slack variables:

$$\sum_s x_{ns} \le 6 \implies \sum_s x_{ns} + \sum_j 2^j y_{nj} = 6$$

Three slack bits per nurse → 36 additional qubits, and squaring produces another ~1,900 terms.

Objective (preferences). 252 linear terms.

Phase 3: The depth consequence

Each QAOA layer applies $e^{-i\gamma H_C}$, requiring one two-qubit rotation per quadratic term:

$$3{,}778 \text{ terms} \times 2 \text{ CNOTs} = 7{,}556 \text{ CNOTs per layer}$$

before routing. The Hamiltonian's interaction graph is dense — nurses within a shift are all-to-all coupled — while hardware is sparse. Realistic SWAP overhead for embedding a dense 288-node graph on heavy-hex is 5–20×:

$$\approx 50{,}000\text{–}150{,}000 \text{ two-qubit gates per layer}$$

At $\epsilon_{2q} = 10^{-3}$, one layer has fidelity $\approx e^{-50} \approx 10^{-22}$.

A single QAOA layer is unrunnable by twenty orders of magnitude. No error mitigation addresses this; it is an error-correction-scale requirement for $p=1$ on a mid-sized scheduling problem.

Phase 4: The penalty-weight problem

Set aside hardware entirely — the encoding has a second, subtler defect.

The penalty weights $A$ and $B$ must be large enough that violating a constraint is never worthwhile, but large weights compress the objective's energy scale relative to the penalties. If $A$ is 100× the preference weights, the optimizer's landscape is dominated by feasibility and nearly flat with respect to the thing you actually want to optimize.

There is no principled way to choose $A$; it is tuned empirically per instance. And the tuning interacts with shot noise, since distinguishing energies that differ by the objective scale requires precision finer than the penalty scale — inflating the measurement budget by the ratio of the two.

Phase 5: Feasible-fraction collapse

Count the search space. $2^{288}$ total assignments. Feasible ones satisfy coverage exactly: $\binom{12}{3}^{21} = 220^{21} \approx 10^{49}$, against $2^{288} \approx 5\times10^{86}$.

$$\text{Feasible fraction} \approx 10^{-38}$$

QAOA samples from the whole space and relies on the cost Hamiltonian to concentrate amplitude on good solutions. Starting from a uniform superposition, essentially all amplitude begins on infeasible garbage, and the penalty terms must move it — which is precisely what large $p$ would accomplish and what hardware cannot afford.

By contrast, a classical constraint solver never leaves the feasible region. Constraint propagation makes infeasible assignments unreachable rather than merely expensive. This is the same structural advantage from the Grover scheduling case study (Chapter 13), appearing again: classical solvers exploit structure that black-box amplitude amplification cannot see.

Alternative worth knowing: XY-mixers and other constraint-preserving mixers restrict QAOA's evolution to the feasible subspace, eliminating penalty terms entirely. They are elegant, they reduce the encoding overhead substantially, and they require more complex mixer circuits — an active research direction that improves the picture without changing the depth verdict here.

Phase 6: The recommendation

Do not encode this problem for QAOA. It needs 288 qubits, ~3,800 Hamiltonian terms, ~50,000+ two-qubit gates per layer, empirical penalty tuning, and it starts with $10^{-38}$ of its amplitude on feasible states.

The classical baseline: OR-Tools CP-SAT solves nurse-scheduling instances of this size to proven optimality in seconds, natively handling equality, inequality, and implication constraints without penalties or slack variables.

The transferable lesson: when evaluating any QAOA application proposal, compute the encoding overhead first. Count qubits after slack variables, count Hamiltonian terms after expanding penalties, and multiply by connectivity overhead. The result usually settles the question before the algorithm is discussed at all.

Discussion Questions

1. Equality constraints expand into $O(n^2)$ quadratic terms. What does that imply for problems with many such constraints?
2. Penalty weights trade feasibility against objective resolution. Is there a principled choice, and what would it depend on?
3. The feasible fraction was $10^{-38}$. Explain why that is fatal for QAOA and harmless for a CP solver.
4. Constraint-preserving mixers avoid penalties. What do they cost, and would they change the verdict here?

Your Turn: Extensions

• Encode a small nurse-scheduling instance (4 nurses, 6 shifts) as a QUBO and count qubits and terms.
• Sweep the penalty weight and plot feasible fraction against objective quality.
• Implement an XY-mixer for a one-hot-constrained problem and compare term counts.
• Solve the same instance with OR-Tools CP-SAT and compare wall-clock.

Key Takeaways

• Real constrained problems require penalty encoding and slack variables, inflating qubit count and producing dense Hamiltonians with thousands of terms.
• Each QAOA layer needs one two-qubit rotation per quadratic term, so encoding overhead translates directly into unrunnable depth.
• Penalty weights must be tuned empirically and trade feasibility against objective resolution, inflating the measurement budget.
• Feasible fractions of $10^{-38}$ are routine; QAOA must move amplitude out of infeasible space, while classical solvers never enter it.
• Compute encoding overhead before evaluating the algorithm — it usually decides the question on its own.