Partitioning transportation networks into balanced and spatially coherent traffic zones is a fundamental yet computationally challenging task in intelligent transportation systems. The resulting optimization problem exhibits dense interactions among decision variables and can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) model. While quantum optimization naturally aligns with such quadratic energy representations, current noisy intermediate-scale quantum hardware imposes limitations on problem size, connectivity, and circuit reliability. This paper proposes an impact-driven hybrid quantum--classical optimization framework for traffic zone partitioning that bridges transportation-scale optimization models and practical gate-based quantum processors. Instead of static geographic decomposition, the method estimates the energy impact of decision variables and selectively assigns quantum computation to influential subproblems while a classical coordination loop maintains global feasibility. The framework is implemented using the Iskay optimizer and evaluated on the IBM Quantum System One backend. Experiments compare direct quantum optimization, classical iterative SubQUBO refinement, and the proposed hybrid approach. Results show that impact-guided decomposition improves convergence behavior and produces more coherent spatial partitions relative to classical refinement, while remaining consistent with hardware constraints. Although the hybrid method does not outperform the best direct quantum solution, it demonstrates a practical pathway toward scalable hybrid optimization for transportation applications under current quantum hardware conditions.
Journal reference
The IEEE International Conference on Intelligent Transportation Systems (ITSC), 2026
Partitioning transportation networks into balanced and spatially coherent traffic zones is a fundamental yet computationally challenging task in intelligent transportation systems. The resulting optimization problem exhibits dense interactions among decision variables and can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) model. While quantum optimization naturally aligns with such quadratic energy representations, current noisy intermediate-scale quantum hardware imposes limitations on problem size, connectivity, and circuit reliability. This paper proposes an impact-driven hybrid quantum--classical optimization framework for traffic zone partitioning that bridges transportation-scale optimization models and practical gate-based quantum processors. Instead of static geographic decomposition, the method estimates the energy impact of decision variables and selectively assigns quantum computation to influential subproblems while a classical coordination loop maintains global feasibility. The framework is implemented using the Iskay optimizer and evaluated on the IBM Quantum System One backend. Experiments compare direct quantum optimization, classical iterative SubQUBO refinement, and the proposed hybrid approach. Results show that impact-guided decomposition improves convergence behavior and produces more coherent spatial partitions relative to classical refinement, while remaining consistent with hardware constraints. Although the hybrid method does not outperform the best direct quantum solution, it demonstrates a practical pathway toward scalable hybrid optimization for transportation applications under current quantum hardware conditions.
Near-term quantum optimizers accommodate roughly a hundred binary variables, requiring large Quadratic Unconstrained Binary Optimization problems to be decomposed into hardware-sized subproblems while other variables remain fixed. Variables are typically selected by ranking the objective changes from individual flips. We show that this rule is uninformative once the incumbent is optimal under single-variable flips: every score represents a cost, while remaining improvements depend on overlooked pairwise interactions. A second-order expansion instead yields a prize-collecting densest-subgraph selection problem, solvable greedily in time linear in the number of variables, and two solver-free bounds bracketing the improvement achievable within a selected subset. On transportation networks from Chicago and Philadelphia, our rule with 16-variable subproblems outperforms random selection with 64, demonstrating that quadrupling device capacity cannot compensate for weaker selection. Replacing geometric adjacency with road-network connectivity widens the margin by a factor of 1.6-1.9. With the selection trace fixed, varying the fraction of subproblems solved on a 120-qubit device from zero to one leaves the final objective unchanged to six significant figures. At tested hardware-accessible sizes, gains therefore arise from selection rather than the backend. Hardware feasibility is limited by coupling terms: 120-variable problems fail to compile with 7,260 terms but succeed with 5,118. Compilation scales almost quadratically with term count and dominates execution cost, reaching 1,752 seconds versus 469 seconds of quantum processing.
Large-scale combinatorial optimization is a challenge for near-term quantum computing because dense Quadratic Unconstrained Binary Optimization (QUBO) formulations yield interaction graphs that exceed the limits of NISQ processors. This work introduces Hybrid Quantum Neighborhood Selection (HQNS), a hybrid framework mitigating this via stochastic frontier decomposition. Instead of encoding all N variables into a monolithic circuit, HQNS selects a compact frontier of F << N active variables per stage, freezing the rest into reduced QUBO coefficients. A multi-stage crawling procedure rotates these frontiers, letting local quantum subproblems refine a global solution. We evaluate HQNS on the Maximum Diversity Subset Selection Problem (MDSSP) across six scales, N up to 1000. Circuit burden is reduced from the dense QAOA requirement of O(N^2) two-qubit terms per layer to O(F^2) per stage, with total complexity governed by the number of stages and classical overhead. Benchmarks show that HQNS achieves competitive solution quality relative to parallel simulated annealing (SA) while maintaining bounded circuit width and stable QPU time. In the N=1000 benchmark over ten executions, HQNS preserves 99.9908% of the mean diversity score of an 11-restart parallel SA baseline, while reducing wall-clock time by 65.03%, peak CPU usage by 55.97%, and peak memory by 35.21%. Ablation shows performance depends on frontier size, warm-starts, CVaR filtering, and stochastic rotation. These results demonstrate that structured frontier decomposition makes variational optimization executable for dense QUBO instances unsuitable for direct QAOA on present hardware.
Complex optimization problems, such as traffic routing and electric vehicle (EV) charging scheduling, are becoming increasingly challenging for intelligent transportation systems (ITSs), in particular as computational resources are limited and network conditions evolve frequently. This paper explores a quantum computing approach to address these issues by proposing a hybrid quantum-classical (HQC) workflow that leverages the variational quantum eigensolver (VQE), an algorithm particularly well suited for execution on noisy intermediate-scale quantum (NISQ) hardware. To this end, the EV charging scheduling and traffic routing problems are both reformulated as binary optimization problems and then encoded into Ising Hamiltonians. Within each VQE iteration, a parametrized quantum circuit (PQC) is prepared and measured on the quantum processor to evaluate the Hamiltonian’s expectation value, while a classical optimizer—such as COBYLA, SPSA, Adam, or RMSProp—updates the circuit parameters until convergence. In order to find optimal or nearly optimal solutions, VQE uses PQCs in combination with classical optimization algorithms to iteratively minimize the problem Hamiltonian. Simulation results exhibit that the VQE-based method increases the efficiency of EV charging coordination and improves route selection performance. These results demonstrate how quantum computing will potentially advance optimization algorithms for next-generation ITSs, representing a practical step toward quantum-assisted mobility solutions.
Scalable combinatorial optimization under resource-constrained quantum hardware remains a fundamental challenge in the Noisy Intermediate-Scale Quantum (NISQ) era, due to the mismatch between exponentially growing solution spaces and limited quantum computational capacity. In this work, we propose a NISQ-aware hybrid quantum-classical optimization framework that reformulates large-scale combinatorial optimization as a resource-bounded distribution evolution process. Instead of directly optimizing individual solutions, the proposed framework operates on a probabilistic representation of the solution space, enabling efficient exploration under hardware constraints. Specifically, large problem instances are decomposed into qubit-compatible subproblems via clustering-based decomposition, ensuring resource-bounded optimization. Within each subproblem, a quantum genetic algorithm evolves the solution distribution, while periodically embedded amplitude amplification acts as a controlled quantum enhancement mechanism that accelerates convergence without increasing circuit depth. A classical refinement stage ensures global solution consistency. Extensive experiments on benchmark and synthetic datasets demonstrate that the proposed framework consistently outperforms classical and quantum-inspired baselines, with performance gains that become more pronounced as problem scale increases. This scale-dependent behavior indicates that scalability is achieved through structured decomposition rather than increased quantum complexity. Noise simulations further confirm robustness under realistic NISQ conditions, and ablation studies validate that both quantum evolutionary search and amplitude amplification contribute significantly to performance improvements.
As quantum computing advances, quantum approximate optimization algorithms (QAOA) have shown promise in addressing combinatorial optimization problems. However, the limitations of Noisy Intermediate Scale Quantum (NISQ) devices hinder the scalability of QAOA for large-scale optimization tasks. To overcome these challenges, we propose Backbone-Driven QAOA, a hybrid framework that leverages adaptive Tabu search for classical preprocessing to decompose large-scale quadratic unconstrained binary (QUBO) problems into NISQ-compatible subproblems. In our approach, adaptive Tabu search dynamically identifies and fixes backbone variables to construct reduced-dimensional subspaces that preserve the critical optimization landscape. These quantum-tractable subproblems are then solved via QAOA, with the resulting solutions iteratively refining the backbone selection in a closed-loop quantum-classical cycle. Experimental results demonstrate that our approach not only competes with, and in some cases surpasses, traditional classical algorithms but also performs comparably with recently proposed hybrid classical-quantum algorithms. Our proposed framework effectively orchestrates the allocation of quantum and classical resources, thereby enabling the solution of large-scale combinatorial optimization problems on current NISQ hardware.
Traffic congestion continues to pose a significant challenge in urban environments, necessitating innovative approaches to traffic management. This paper explores the application of Quantum Annealing (QA) for real-world traffic optimization, expanding on the pioneering work of Volkswagen and D-Wave. In 2017, a collaborative team demonstrated the potential of QA to optimize traffic flow by solving a complex Quadratic Unconstrained Binary Optimization (QUBO) problem involving 418 cars, which required 1,254 qubits. Later, this research culminated in a pilot project at the Web Summit conference in Lisbon, one of Europe's largest technology events, showcasing quantum computing-based traffic optimization. Since the QPU alone could not directly handle the full problem size, the team employed a hybrid classical-quantum approach, leading to significant improvements in traffic distribution. This paper builds on that foundation by investigating potential speedups using a purely quantum approach, particularly by utilizing the QPU for smaller QUBO problems. The proposed method (MTF) enhances traffic management by decomposing the overall optimization problem into smaller, more manageable subproblems. This decomposition enables us to harness the advantages of the QPU while tackling more complex traffic scenarios that previous approaches struggled to manage. By breaking the problem into smaller parts, we mitigate the challenges associated with embedding large-scale problems into the QPU, which often presents computational difficulties. To evaluate our approach, we conducted experiments involving 100, 200, 300, 400, and 500 cars on a complex traffic map featuring multiple start and end points. We successfully embedded the problem into the D-Wave Advantage Quantum Processing Unit, utilizing the "Pegasus" topology, which resulted in a significant acceleration of the solution process. The experiment results show improved speed and effectiveness in real-world scenarios by leveraging the QPU for better traffic optimization.