Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer
Talha Azfar, Osama Muhammad Raisuddin, Ruimin Ke, José Holguín-Veras · 2025
Read Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer by Talha Azfar, Osama Muhammad Raisuddin, Ruimin Ke, José Holguín-Veras (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-01614.txt.
Introduction
Talha Azfar and co-authors wrote a 2025 paper on running a delivery route solver on a real quantum computer. Routing vehicles well is a classic hard puzzle in logistics. Their method folds route rules, like flow balance and no stray loops, straight into the cost setup of a quantum search algorithm.
The full chain, from problem setup to circuit run, was executed on an IBM quantum machine. Small cases show how penalty weights, scaling, and circuit depth sway whether answers stay valid under hardware noise. Scale is capped by noise and decay for now. The authors map the path for near term quantum logistics work.
Catalog record
| CREATOR | Talha Azfar, Osama Muhammad Raisuddin, Ruimin Ke, José Holguín-Veras |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-01614
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer Talha Azfar, Osama Muhammad Raisuddin, Ruimin Ke, José Holguín-Veras Abstract . The Vehicle Routing Problem (VRP) is a fundamental combinatorial optimization challenge with broad applications in logistics and transportation. In this work, we present a quantum-assisted framework that integrates the Quantum Approximate Optimization Algorithm (QAOA) with a link-based formulation of VRP. Our approach encodes flow conservation and subtour elimination directly into the cost Hamiltonian, preserving graph structure while minimizing resource requirements for practical hardware implementation. We design and implement the full pipeline on a gate-based quantum computer, including problem formulation, encoding, circuit synthesis, and execution on IBM Quantum System One. Experimental results on small VRP instances highlight the effects of penalty scaling, coefficient normalization, and circuit depth on solution feasibility under hardware noise. While scalability remains constrained by circuit complexity and decoherence, the study demonstrates a practical pathway for implementing VRP on quantum hardware and identifies methodological directions for advancing near-term quantum optimization. CCS: Computer systems organization Quantum computing CCS: General and reference Experimentation CCS: Mathematics of computing Combinatorial optimization 1. Introduction Metropolitan areas generate over 60% of global GDP but account for nearly 70% of fossil fuel-related CO 2 emissions ( NASA, 2024 ) , underscoring the dual challenge of economic growth and environmental externalities. Urban logistics optimization is central to mitigating congestion and inefficiencies while promoting sustainability ( He et al., 2023 ) , yet remains complex due to numerous variables and constraints. At its core lies the Vehicle Routing Problem (VRP, a fundamental NP-hard extension of the Traveling Salesman Problem (TSP) ( Clarke and Wright, 1964 ; Jünger et al., 1995 ) , which seeks efficient vehicle routes to minimize costs such as distance, fuel, or time, and has broad applications from last mile delivery to large scale freight distribution. VRP instances arise in logistics and transportation planning, from last-mile delivery to large-scale distribution, and even modest-sized instances are NP-hard and computationally intractable to solve optimally with classical algorithms. This motivates exploring alternative computing paradigms for VRP and similar combinatorial problems. In particular, quantum computing has emerged as a promising paradigm for tackling NP-hard problems by exploiting quantum superposition and entanglement to potentially search huge solution spaces more efficiently. Although current quantum devices operate in the noisy intermediate-scale quantum (NISQ) regime with only tens to hundreds of qubits and significant noise, the field is advancing rapidly ( Preskill, 2018 ) . Quantum algorithms for optimization, if carefully designed to work within these hardware limits, could eventually augment classical high-performance computing (HPC) in solving real-world optimization tasks. Figure 1 . Solving the VRP using QAOA involves a formulation of the link based constrained minimization form to the unconstrained quadratic binary representation, which is then cast as an Ising Hamiltonian required for QAOA. The high level circuit is transpiled into one and two qubit basic gates for implementation on the IBM-Rensselaer quantum computer. The circuit is run repeatedly to optimize the variational parameters, and a final sampling provides the solution. The problem graph shown here is for illustrative purposes only. Section 4 describes a specific example problem. One leading approach for combinatorial optimization on gate-based quantum computers is the Quantum Approximate Optimization Algorithm (QAOA) ( Farhi et al., 2014 ) , inspired by the quantum adiabatic theorem that is fundamental to quantum annealing ( Farhi et al., 2000 ) . QAOA is a hybrid quantum-classical algorithm that encodes an optimization problem into a parameterized quantum circuit and uses a classical optimizer to tune those parameters. By alternating problem specific cost operators and mixing operators on n qubits, QAOA can in principle concentrate probability mass on high quality solutions among the 2^{n} possible states. Its suitability for near-term devices has made QAOA a focal point for studying problems in logistics, finance, and network optimization. Applying QAOA to the VRP is especially enticing because VRP’s graph-structured decision space might be naturally encoded in a quantum Hamiltonian. A quantum enhanced solution to VRP could not only demonstrate the capabilities of NISQ algorithms on a problem of practical relevance, but also pave the way for quantum assisted HPC workflows where classical and quantum resources are integrated to tackle industry-scale optimization ( Elsharkawy et al., 2025 ) . However, significant methodological challenges arise in bringing QAOA to VRP. First, one must devise an encoding of VRP into a quantum-friendly cost function (e.g. a Quadratic Unconstrained Binary Optimization, QUBO) that captures all the problem constraints without exploding the resource requirements. The VRP has complex feasibility constraints: each customer must be visited exactly once, vehicles have route length or capacity limits, and routes must form contiguous tours, which are nontrivial to represent in a qubit Hamiltonian. Naively encoding all constraints can require a large number of qubits or high order penalty terms. Prior attempts have taken different formulation strategies, for example, some works introduced time step indexed decision variables to linearize the route order, thereby restricting the search to classically feasible sequences ( Palackal et al., 2023 ) . This approach can asymptotically reduce the quantum resources needed by eliminating invalid states at the cost of additional ancilla qubits and complex multi-controlled operations. Another approach is to use unbalanced penalty weights for soft constraints, effectively biasing the cost function to discourage violations without strictly forbidding them; but this requires careful tuning of penalty coefficients via classical optimization and can introduce higher order interactions ( Montañez-Barrera et al., 2024 ) . Designing an encoding that is compact yet enforces VRP constraints remains a core challenge. Ensuring solution feasibility is a key challenge when applying QAOA to constrained problems. Since the quantum state explores superpositions of many bitstrings, an unsuitable Hamiltonian or mixer can increase the likelihood of measuring infeasible routes (e.g., routes omitting customers or forming subtours). To address this, researchers have explored customized mixers that restrict the evolution to feasible subspaces, as well as warm-start strategies that initialize QAOA in valid solutions. However, empirical studies on VRP have shown only limited improvements from these techniques ( Fitzek et al., 2024 ) . For example, even in hybrid approaches where classical clustering was used to reduce the problem before applying QAOA, performance remained behind comparable VQE methods, with QAOA struggling to consistently recover feasible solutions in small instances. These findings highlight the ongoing difficulty of steering QAOA effectively toward the feasible region of combinatorial problems. Furthermore, quantum circuit depth and hardware limitations impose severe restrictions on solving VRP with QAOA. Each layer of QAOA applies numerous two qubit gates to implement problem interactions. As the problem size or number of QAOA layers increases, the circuit quickly becomes deeper and more error-prone. Current superconducting quantum processors have limited qubit connectivity and coherence times, meaning complex QAOA circuits suffer from accumulated gate errors and decoherence before completion ( Blekos et al., 2024 ) . For a VRP instance of even modest size, achieving good solution quality might require many layers of QAOA, a regime simply not attainable on today’s hardware. Moreover, qubit count and topology are limiting factors: encoding a VRP with N locations typically involves O(N^{2}) binary decision variables (for example, representing each possible directed edge or each assignment of a location to a route position). This can