Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum-Enhanced LLM Cascade Routing: A QAOA Approach to Cost-Optimal Model Selection in Multi-Agent Systems

AMIT SAMSON PATOLE

Published Apr 7, 2026• 0 citations
Publisher

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

DOI
10.5281/zenodo.19462039

Related papers

Quantum-Enhanced LLM Cascade Routing: A QAOA Approach to Cost-Optimal Model Selection in Multi-Agent Systems

Amit Patole

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.

•Apr 7, 2026•0 citations

Quantum-Enhanced LLM Cascade Routing: A QAOA Approach to Cost-Optimal Model Selection in Multi-Agent Systems

Amit Patole

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.

•Apr 9, 2026•0 citations

Applying the Quantum Approximate Optimization Algorithm to the UAV Collision Avoidance Problem

Kalleb C. Santos, Maria Eduarda W. M. Vianna, Mateus K. de Oliveira +4 more

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.

Simpósio Brasileiro de Computação e Comunicação Quânticas (SBCCQ)•Jul 19, 2026•0 citations

Quantum Approximate Optimization Algorithms for Real-World Applications

Erik Lindberg, Ivan Lindberg

The Quantum Approximate Optimisation Algorithm (QAOA) has emerged as a leading candidate for near-term quantum advantage in combinatorial optimisation, but most evaluations remain confined to synthetic benchmarks such as random MaxCut instances. Translating QAOA to real-world problem instances -- with irregular graph structures, heterogeneous constraint types, and practical scale requirements -- introduces additional challenges including QUBO formulation overhead, hardware embedding costs, and the performance gap between QAOA on structured real instances vs. random benchmarks. This paper presents the Real-World QAOA (RW-QAOA) framework, a systematic methodology for applying QAOA to four real-world application domains: supply chain network optimisation, financial portfolio rebalancing, telecommunications frequency assignment, and traffic signal timing optimisation. RW-QAOA introduces three methodological contributions: a domain-adaptive QUBO formulator (DAQF) encoding real-world constraints as penalised QUBO terms with penalty coefficient auto-tuning; a warm-start initialisation strategy (WSIS) using classical heuristic solutions to seed QAOA parameter search; and a layered noise adaptation protocol (LNAP) adjusting circuit depth based on real-time device calibration data. RW-QAOA is evaluated on real problem instances from industry partners across all four domains on IBM Quantum Eagle (127-qubit). RW-QAOA achieves solution quality within 4.2% of classical exact solvers across all four domains, outperforming classical greedy heuristics by 12.4% (SD = 3.8%) on average. WSIS reduces QAOA parameter convergence iterations by 48.4%. LNAP improves approximation ratio by 8.4pp vs. fixed-depth QAOA under device noise variation.

Quantum Frontiers Journal•Mar 28, 2024•0 citations

Towards quantum-ready optimization: A QUBO model for task assignment to autonomous mobile robots

Ole Christian Prüfer, Jens Heger

Autonomous Mobile Robots (AMRs) play an increasingly important role in flexible and reconfigurable production systems. Assigning heterogeneous tasks to multiple AMRs constitutes a combinatorial optimization problem that becomes computationally intractable as system complexity grows. This paper presents a Quadratic Unconstrained Binary Optimization (QUBO) model for AMR task assignment, integrating scheduling and resource allocation within a Hamiltonian formulation. The model is parameterized and evaluated using both exact and heuristic solvers to analyze scalability and validity across benchmark scenarios. Results demonstrate the trade-off between computational effort and solution optimality, confirming the feasibility of the QUBO representation for this problem class. The formulated model creates a basis for future implementation on quantum hardware for optimization using Quantum Annealing (QA) or the Quantum Approximate Optimization Algorithm (QAOA), thereby bridging the gap between classical optimization methods and new quantum computing paradigms.

Procedia CIRP•Jan 1, 2026•0 citations

Quantum Algorithms for Discrete and Combinatorial Optimization

Gloria Oppong

This study explores quantum computing for combinatorial optimization, focusing on the Traveling Salesman Problem (TSP). Using Qiskit, the Quantum Approximate Optimization Algorithm (QAOA) is implemented on simulators and quantum hardware, and compared with classical optimization using Gurobi. TSP instances are encoded as Quadratic Unconstrained Binary Optimization (QUBO) problems derived from the Miller–Tucker–Zemlin formulation, with quadratic penalties enforcing degree and subtour constraints. Results indicate that QAOA consistently generates feasible tours, but classical branch-and-bound methods achieve better solution quality and runtime. On Noisy Intermediate-Scale Quantum (NISQ) devices, performance degrades with problem size due to sensitivity to parameter tuning, penalty scaling, and hardware noise. Among the tested classical optimizers, COBYLA provides the best balance of efficiency and noise tolerance. Overall, this work establishes a reproducible quantum-classical workflow, provides performance baselines, and identifies critical factors such as encoding design, optimizer choice, and error mitigation for improving near-term quantum heuristic performance.

•May 5, 2026•0 citations
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
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 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.
The Quantum Approximate Optimisation Algorithm (QAOA) has emerged as a leading candidate for near-term quantum advantage in combinatorial optimisation, but most evaluations remain confined to synthetic benchmarks such as random MaxCut instances. Translating QAOA to real-world problem instances -- with irregular graph structures, heterogeneous constraint types, and practical scale requirements -- introduces additional challenges including QUBO formulation overhead, hardware embedding costs, and the performance gap between QAOA on structured real instances vs. random benchmarks. This paper presents the Real-World QAOA (RW-QAOA) framework, a systematic methodology for applying QAOA to four real-world application domains: supply chain network optimisation, financial portfolio rebalancing, telecommunications frequency assignment, and traffic signal timing optimisation. RW-QAOA introduces three methodological contributions: a domain-adaptive QUBO formulator (DAQF) encoding real-world constraints as penalised QUBO terms with penalty coefficient auto-tuning; a warm-start initialisation strategy (WSIS) using classical heuristic solutions to seed QAOA parameter search; and a layered noise adaptation protocol (LNAP) adjusting circuit depth based on real-time device calibration data. RW-QAOA is evaluated on real problem instances from industry partners across all four domains on IBM Quantum Eagle (127-qubit). RW-QAOA achieves solution quality within 4.2% of classical exact solvers across all four domains, outperforming classical greedy heuristics by 12.4% (SD = 3.8%) on average. WSIS reduces QAOA parameter convergence iterations by 48.4%. LNAP improves approximation ratio by 8.4pp vs. fixed-depth QAOA under device noise variation.
Autonomous Mobile Robots (AMRs) play an increasingly important role in flexible and reconfigurable production systems. Assigning heterogeneous tasks to multiple AMRs constitutes a combinatorial optimization problem that becomes computationally intractable as system complexity grows. This paper presents a Quadratic Unconstrained Binary Optimization (QUBO) model for AMR task assignment, integrating scheduling and resource allocation within a Hamiltonian formulation. The model is parameterized and evaluated using both exact and heuristic solvers to analyze scalability and validity across benchmark scenarios. Results demonstrate the trade-off between computational effort and solution optimality, confirming the feasibility of the QUBO representation for this problem class. The formulated model creates a basis for future implementation on quantum hardware for optimization using Quantum Annealing (QA) or the Quantum Approximate Optimization Algorithm (QAOA), thereby bridging the gap between classical optimization methods and new quantum computing paradigms.
This study explores quantum computing for combinatorial optimization, focusing on the Traveling Salesman Problem (TSP). Using Qiskit, the Quantum Approximate Optimization Algorithm (QAOA) is implemented on simulators and quantum hardware, and compared with classical optimization using Gurobi. TSP instances are encoded as Quadratic Unconstrained Binary Optimization (QUBO) problems derived from the Miller–Tucker–Zemlin formulation, with quadratic penalties enforcing degree and subtour constraints. Results indicate that QAOA consistently generates feasible tours, but classical branch-and-bound methods achieve better solution quality and runtime. On Noisy Intermediate-Scale Quantum (NISQ) devices, performance degrades with problem size due to sensitivity to parameter tuning, penalty scaling, and hardware noise. Among the tested classical optimizers, COBYLA provides the best balance of efficiency and noise tolerance. Overall, this work establishes a reproducible quantum-classical workflow, provides performance baselines, and identifies critical factors such as encoding design, optimizer choice, and error mitigation for improving near-term quantum heuristic performance.