Quantum-Enhanced LLM Cascade Routing: A QAOA Approach to Cost-Optimal Model Selection in Multi-Agent Systems
AMIT SAMSON PATOLE
Abstract
The rapid proliferation of large language model(LLM) powered multi-agent systems creates a non-trivial combinatorialoptimization problem: routing heterogeneous tasksto the most cost-effective model tier while maintaining qualityguarantees. Current production systems rely on static lookuptables, which over-provision expensive models and waste computationalbudget. We formalize the LLM Cascade Routing Problem(LCRP) as a Quadratic Unconstrained Binary Optimization(QUBO) problem and solve it using the Quantum ApproximateOptimization Algorithm (QAOA). We benchmark QAOA againstgreedy heuristics and simulated annealing using both Google Cirqsimulation and real IBM Quantum hardware (156-qubit Heronprocessors). Experiments across three IBM backends (ibm fez,ibm kingston, ibm marrakesh) on problem instances from 6 to18 qubits reveal three key findings: (i) shallow QAOA circuits(p=1, depth 52) achieve 24–25% valid assignment rate on realhardware versus <1% for deeper circuits (p = 2, depth 101),a 25× improvement reproduced across all three backends; (ii)hardware constraint satisfaction degrades steeply with problemsize, dropping from 24–26% at 6 qubits to 0.9–1.4% at 18qubits for p = 1; and (iii) results are reproducible across allthree backends with consistent valid rates within ±0.5% at12 qubits. We further evaluate warm-start initialization fromclassical solutions and feasibility-first decoding, demonstratingthat post-processing can recover 100% valid assignments fromnoisy hardware output. To our knowledge, this is the firstquantum computing formulation of the LLM model routingproblem. We provide an open-source implementation with 28verifiable IBM Quantum job IDs.Index Terms—Quantum Computing, QAOA, LLM Routing,Multi-Agent Systems, Combinatorial Optimization, QUBO, NISQ