QAOA vs. Classical Solvers — A Full-Pipeline, Honest Benchmark

The problem, and what the data actually is

Exam scheduling is a conflict-minimization problem — no two subjects sharing enough students can share a session slot — and we mapped it as a weighted Max-Cut problem, the same shape as the scheduling conflicts Gurukul Academy's Exam Management module handles. To be direct about provenance: the benchmark itself runs on a synthetic dataset (558 students, 42 subjects, 459 weighted conflict edges) constructed to mirror realistic enrollment patterns, not pulled from a live production run. We're flagging that plainly because it changes how the result should be read — this measures algorithm and hardware behavior on a realistically structured instance, not a deployed outcome.

Method

• Five solvers compared on the same 42-subject problem: random assignment, a greedy heuristic, 2-opt local search, an exact integer LP (Google OR-Tools), and QAOA
• QAOA validated first on an 18-qubit subgraph via noisy local simulation (matrix-product-state, seeded with a real IBM backend's noise model) before spending any hardware budget
• One tuned, high-shot (4,096-shot) submission to IBM's ibm_marrakesh device (Heron r2) at the full 42-qubit problem size
• Every stochastic result scored by shot-weighted expected value, not best-single-shot — with thousands of shots, some beat the average by chance alone, and reporting only that number overstates performance

Results

• 18 qubits (local noisy simulation): QAOA reached 95.4% of the proven optimum, against 99.3% for greedy and 100% for the exact solver
• 42 qubits (real hardware): QAOA's expected value came in at 49.05% of total conflict weight — below the 50.00% random baseline. The best single shot (55.79%) was comparable to greedy's 55.80%, but occurred in only 1 of 4,096 shots, and isn't representative of the distribution as a whole
• All 4,096 measurement shots returned distinct bitstrings — no outcome repeated even once, the statistical signature of decoherence overwhelming the circuit before measurement, not an algorithm that converged incorrectly

Why it fails at 42 qubits

One qubit per subject, at this density, forces a transpiled circuit depth of 2,946 gates. Per-gate error on ibm_marrakesh compounds multiplicatively over that many sequential gates, and total circuit execution time ends up exceeding the qubits' coherence window — so the state read out at measurement has been scrambled by environmental noise rather than shaped by the algorithm. That directly explains the all-distinct-bitstrings result, and it's consistent with the 18-qubit result holding up once depth is a fifth of the size.

What's next

The natural next step is a direct comparison against D-Wave quantum annealing hardware on the identical problem instance — an architecturally different paradigm, native to Max-Cut/QUBO problems, that doesn't accumulate gate-sequence error the way this pipeline's circuit does. We'll apply the same expected-value scoring methodology to keep the comparison honest and consistent across paradigms. Full pipeline code is available on request.