Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910001393565696 |
|---|---|
| author | Azfar, Talha Raisuddin, Osama Muhammad Ke, Ruimin Holguin-Veras, Jose |
| author_facet | Azfar, Talha Raisuddin, Osama Muhammad Ke, Ruimin Holguin-Veras, Jose |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_01614 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer Azfar, Talha Raisuddin, Osama Muhammad Ke, Ruimin Holguin-Veras, Jose Quantum Physics Emerging Technologies 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. |
| title | Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer |
| topic | Quantum Physics Emerging Technologies |
| url | https://arxiv.org/abs/2505.01614 |