QAOA for Scheduling Problems
Encoding job assignment and ordering constraints as an Ising cost function for the Quantum Approximate Optimization Algorithm.
Scheduling as optimization
Scheduling assigns tasks to time slots or machines subject to constraints: no two tasks on the same machine at the same time, precedence between dependent tasks, and a resource limit per slot. The objective is often to minimize makespan (total completion time) or the number of constraint violations. These problems are combinatorial and typically NP-hard.
Binary encoding
A common encoding uses one binary variable x_{t,s} = 1 if task t occupies slot s. Constraints become penalty terms: each task in exactly one slot gives (sum_s x_{t,s} - 1)^2; a machine capacity of one per slot gives sum over conflicting pairs x_{t,s} x_{t',s}. Precedence that task a finishes before task b starts adds penalties for orderings that violate it. The total is a QUBO, mapped to an Ising Hamiltonian via x = (1 - Z)/2.
Cost structure
- One-hot penalties enforce valid assignments.
- Pairwise conflict penalties forbid double-booking a resource.
- Precedence penalties encode task dependencies.
- An optional soft term rewards shorter makespan.
Solving with QAOA
The resulting Ising Hamiltonian H_C drives depth-p QAOA with the standard transverse-field mixer, or an XY mixer that respects one-hot structure to stay in the feasible subspace. The classical optimizer tunes the angles to minimize expected energy; sampling the optimized state yields candidate schedules, which are checked for feasibility and ranked.
Scaling considerations
The number of qubits grows with tasks times slots, so encoding is the main bottleneck. Slot pruning, domain reduction, and hybrid decomposition (solve subproblems classically, stitch with QAOA) keep instances tractable on near-term devices. As with other QAOA applications, results depend strongly on depth p, angle initialization, and hardware noise. See QAOA parameter optimization.