The rapid proliferation of large language model (LLM) powered multi-agent systems creates a non-trivial combinatorial optimization problem: routing heterogeneous tasks to the most cost-effective model tier while maintaining quality guarantees. Current production systems rely on static lookup tables, which over-provision expensive models and waste computational budget. We formalize the LLM Cascade Routing Problem (LCRP) as a Quadratic Unconstrained Binary Optimization (QUBO) problem and solve it using the Quantum Approximate Optimization Algorithm (QAOA). We benchmark QAOA against greedy heuristics and simulated annealing using both Google Cirq simulation and real IBM Quantum hardware (156-qubit Heron processors). Experiments across three IBM backends (ibm_fez, ibm_kingston, ibm_marrakesh) on problem instances from 6 to 18 qubits reveal three key findings: (i) shallow QAOA circuits (p=1, depth 52) achieve 15.4% valid assignment rate on real hardware versus 0.8% for deeper circuits (p=2, depth 101), demonstrating that NISQ noise favors shallow ansatze; (ii) hardware constraint satisfaction degrades steeply with problem size, dropping from 37-43% at 6 qubits to 0.2-0.3% at 18 qubits; and (iii) results are reproducible across all three backends with consistent valid rates within plus or minus 1.5%. To our knowledge, this is the first quantum computing formulation of the LLM model routing problem. We provide an open-source implementation and discuss the projected quantum advantage horizon.
The rapid proliferation of large language model (LLM) powered multi-agent systems creates a non-trivial combinatorial optimization problem: routing heterogeneous tasks to the most cost-effective model tier while maintaining quality guarantees. Current production systems rely on static lookup tables, which over-provision expensive models and waste computational budget. We formalize the LLM Cascade Routing Problem (LCRP) as a Quadratic Unconstrained Binary Optimization (QUBO) problem and solve it using the Quantum Approximate Optimization Algorithm (QAOA). We benchmark QAOA against greedy heuristics and simulated annealing using both Google Cirq simulation and real IBM Quantum hardware (156-qubit Heron processors). Experiments across three IBM backends (ibm_fez, ibm_kingston, ibm_marrakesh) on problem instances from 6 to 18 qubits reveal three key findings: (i) shallow QAOA circuits (p=1, depth 52) achieve 15.4% valid assignment rate on real hardware versus 0.8% for deeper circuits (p=2, depth 101), demonstrating that NISQ noise favors shallow ansatze; (ii) hardware constraint satisfaction degrades steeply with problem size, dropping from 37-43% at 6 qubits to 0.2-0.3% at 18 qubits; and (iii) results are reproducible across all three backends with consistent valid rates within plus or minus 1.5%. To our knowledge, this is the first quantum computing formulation of the LLM model routing problem. We provide an open-source implementation and discuss the projected quantum advantage horizon.
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
Full-pipeline benchmark of the Quantum Approximate Optimization Algorithm (QAOA) against classical combinatorial solvers on a weighted Max-Cut formulation of exam-scheduling conflict minimization. Compares random assignment, greedy heuristic, 2-opt local search, exact ILP (OR-Tools), and QAOA — first via noisy local simulation on an 18-qubit validation subset, then via live execution on IBM's ibm_marrakesh (Heron r2) processor at the full 42-qubit scale. Uses shot-weighted expected-value scoring throughout rather than best-observed-sample reporting. At 18 qubits QAOA reaches 95.4% of the proven optimum; at 42 qubits the hardware run's expected value falls below random guessing (49.05% vs 50.00%), with all 4,096 shots returning distinct bitstrings — the signature of decoherence overwhelming the circuit. Includes causal analysis of the failure mode and outlines planned comparison against quantum annealing hardware.
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm used to study NP-hard combinatorial optimization problems. In this work, we focused on optimization strategies for QAOA including circuit depth reduction, parameter parallelization, and hybrid classical feedback mechanisms. We will consider the application of QAOA to different types of NP-hard problems such as Max-Cut and Vehicle Routing Problem (VRP) and discuss the advantages and disadvantages of each in terms of approximation quality and cost of computation. The comparative simulation on the various qubit counts and depth layers points out the limits of scalability and the constraints of hardware on the current Noisy Intermediate-Scale Quantum (NISQ) devices. And also an improved divide-and-conquer strategy is presented in which parameter reusability and gradient-informed initialization are combined to boost convergence rates. The results of the experiment show that it is more efficient and scalable while maintaining the competitive approximation performance compared to the baseline QAOA. The experimental validation focuses on representative small-size instances, while the proposed framework provides extensions for scalable implementations. Ultimately, this work is a step towards the realization of efficient, hardware-aware, and scalable optimization strategies, thus opening up the practical deployment of QAOA on the quantum systems of the next few years.
Despite rapid progress in quantum optimization, broad real-hardware benchmarks comparing multiple algorithmic families across diverse combinatorial problems under a common protocol remain limited. We benchmark gate-based quantum optimization on four NP-hard problems: multi-dimensional knapsack (MDKP), maximum independent set (MIS), quadratic assignment (QAP), and market-share (MSP). We study VQE, CVaR-VQE, standard, multi-angle, and warm-start QAOA, together with qubit-efficient PCE and QRAO, on IBM Heron r1/r2 processors using resilience-level-2 mitigation. To our knowledge, this includes the first real-hardware QRAO results and the first multi-problem PCE hardware benchmark.
Across 247 method-instance combinations, we report transpiled circuit size, hardware outcomes, and an independent-error gate-count fidelity proxy,
Fest. For MDKP and MIS, an empirical operating point near
Fest≈0.1, corresponding to about 770 two-qubit gates at the median Heron-r2 CZ error rate, marks the onset of noise-dominated execution. QAP exposes a separate bottleneck: dense one-hot encodings and an exponentially sparse feasible manifold, with feasible fraction
10!/2100 at
n=10; no tested hardware method produces a feasible assignment. Compiled QAOA-family circuits are generally noise dominated, and a matched uniform-random control shows that most feasible low-fidelity outcomes fall within the random range, apart from one finite-sample MIS warm-start exception. A SWAP-aware, fractional-gate, Nighthawk-topology compilation counterfactual reduces two-qubit counts but leaves all circuits below
Fest=10−3. These conclusions apply to the tested implementations rather than QAOA in general. Qubit-efficient methods extend runnable instance sizes, but only within the empirical fidelity budget.
The increasing availability of quantum hardware has stimulated interest in applying quantum algorithms to combinatorial optimization problems. Collision avoidance for unmanned aerial vehicles (UAVs) is one such challenge due to the computational complexity of coordinating multiple agents in shared airspace. In this paper, we formulate the problem as a Quadratic Unconstrained Binary Optimization (QUBO) model that captures route selection and collision constraints, enabling the use of the Quantum Approximate Optimization Algorithm (QAOA). To improve efficiency, we introduce a constrained QAOA Ansatz employing an XY-mixer that preserves one-hot route assignment constraints and restricts the search space to valid solutions. We evaluate the approach through noiseless simulations and device-based noise models, analyzing its behavior under realistic conditions and highlighting the opportunities and limitations of near-term quantum hardware for multi-agent routing problems.