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

Lecture notes in networks and systems

Quantum Computing for Graph Optimization: An Approach to the Shortest Path Problem

Aniket Bembale, Nagendra Singh, P. Vinayaka, Jitesh Choudhary

Published Dec 1, 2025• 0 citations
Publisher
DOI
10.1007/978-981-95-0681-1_27

Related papers

Modeling of shortest path of a graph in quantum computing

Nongmeikapam Brajabidhu Singh, Joseph L. Pachuau, Anish Kumar Saha

The Journal of Supercomputing•Oct 14, 2025•1 citation

Solving the Shortest Path Problem with QAOA

Zhiqiang Fan, Jinchen Xu, Guoqiang Shu +3 more

Graph computation is a core technique for solving realistic problems of graph representations. In solving the shortest path problem (SPP), the current classical methods are encountering a huge performance bottleneck. Attempting to solve this dilemma, we try to solve the SPP with a Quantum Approximate Optimal Algorithm (QAOA)-based quantum method. In this paper, we propose a QAOA-based shortest path algorithm (SPA) by constructing a suitable Hamiltonian quantity and using the idea of variational quantum computing, and verify the algorithm using a quantum simulator and an International Business Machines cloud quantum computer. The proposed algorithm is able to achieve a near-optimal solution with a correct rate that significantly exceeds the invalid solutions, reaching a good preliminary result. Furthermore, the proposed algorithm is expected to achieve a huge advantage over the classical algorithm and the SPA based on Grover’s algorithm with a suitable selection of parameters and number of steps. In addition, the proposed algorithm requires fewer quantum bits than other quantum algorithms, thus promising quantum computing superiority on current noisy intermediate-scale quantum (NISQ) quantum computing devices.

SPIN•Dec 9, 2022•5 citations

Solving the Network Shortest Path Problem on a Quantum Annealer

Thomas Krauss, Joey McCollum

This article addresses the formulation for implementing a single source, single-destination shortest path algorithm on a quantum annealing computer. Three distinct approaches are presented. In all the three cases, the shortest path problem is formulated as a quadratic unconstrained binary optimization problem amenable to quantum annealing. The first implementation builds on existing quantum annealing solutions to the traveling salesman problem, and requires the anticipated maximum number of vertices on the solution path |P| to be provided as an input. For a graph with |V| vertices, |E| edges, and no self-loops, it encodes the problem instance using |V||P| qubits. The second implementation adapts the linear programming formulation of the shortest path problem, and encodes the problem instance using |E| qubits for directed graphs or 2|E| qubits for undirected graphs. The third implementation, designed exclusively for undirected graphs, encodes the problem in |E| + |V| qubits. Scaling factors for penalty terms, complexity of coupling matrix construction, and numerical estimates of the annealing time required to find the shortest path are made explicit in the article.

IEEE Transactions on Quantum Engineering•Jan 1, 2020•34 citations

Quantum Algorithms for Optimization

Ansh Bansal

IOSR Journal of Computer Engineering•Oct 1, 2025•0 citations

QUANTUM PATHFINDERS: NAVIGATE THE SHORTEST ROUTE

Mohammad Sahil, Sapna Jain, Jamia Hamdard

The problem of finding the shortest path between two points in a graph is a fundamental problem in computer science and has many applications in fields such as transportation, logistics, and networking. Dijkstra's algorithm is a classical algorithm commonly used to solve this problem, but its time complexity can be prohibitively high for large graphs. Quantum computing, on the other hand, offers a promising approach to solving this problem with significantly improved time complexity. In this research paper, we explore the potential of quantum computing for solving the shortest path problem, including an overview of Dijkstra's algorithm and its limitations, the quantum computing approach using quantum phase estimation, and a comparison of the time complexities of classical and quantum algorithms. We also discuss the challenges that need to be addressed for quantum computing to realize its potential in solving practical shortest-path problems.

International Journal of Engineering Applied Sciences and Technology•Apr 1, 2023•0 citations

Quantum Graphs and Optimization

Sovan Samanta

Studies in computational intelligence•Jan 1, 2025•0 citations
Graph computation is a core technique for solving realistic problems of graph representations. In solving the shortest path problem (SPP), the current classical methods are encountering a huge performance bottleneck. Attempting to solve this dilemma, we try to solve the SPP with a Quantum Approximate Optimal Algorithm (QAOA)-based quantum method. In this paper, we propose a QAOA-based shortest path algorithm (SPA) by constructing a suitable Hamiltonian quantity and using the idea of variational quantum computing, and verify the algorithm using a quantum simulator and an International Business Machines cloud quantum computer. The proposed algorithm is able to achieve a near-optimal solution with a correct rate that significantly exceeds the invalid solutions, reaching a good preliminary result. Furthermore, the proposed algorithm is expected to achieve a huge advantage over the classical algorithm and the SPA based on Grover’s algorithm with a suitable selection of parameters and number of steps. In addition, the proposed algorithm requires fewer quantum bits than other quantum algorithms, thus promising quantum computing superiority on current noisy intermediate-scale quantum (NISQ) quantum computing devices.
This article addresses the formulation for implementing a single source, single-destination shortest path algorithm on a quantum annealing computer. Three distinct approaches are presented. In all the three cases, the shortest path problem is formulated as a quadratic unconstrained binary optimization problem amenable to quantum annealing. The first implementation builds on existing quantum annealing solutions to the traveling salesman problem, and requires the anticipated maximum number of vertices on the solution path |P| to be provided as an input. For a graph with |V| vertices, |E| edges, and no self-loops, it encodes the problem instance using |V||P| qubits. The second implementation adapts the linear programming formulation of the shortest path problem, and encodes the problem instance using |E| qubits for directed graphs or 2|E| qubits for undirected graphs. The third implementation, designed exclusively for undirected graphs, encodes the problem in |E| + |V| qubits. Scaling factors for penalty terms, complexity of coupling matrix construction, and numerical estimates of the annealing time required to find the shortest path are made explicit in the article.
The problem of finding the shortest path between two points in a graph is a fundamental problem in computer science and has many applications in fields such as transportation, logistics, and networking. Dijkstra's algorithm is a classical algorithm commonly used to solve this problem, but its time complexity can be prohibitively high for large graphs. Quantum computing, on the other hand, offers a promising approach to solving this problem with significantly improved time complexity. In this research paper, we explore the potential of quantum computing for solving the shortest path problem, including an overview of Dijkstra's algorithm and its limitations, the quantum computing approach using quantum phase estimation, and a comparison of the time complexities of classical and quantum algorithms. We also discuss the challenges that need to be addressed for quantum computing to realize its potential in solving practical shortest-path problems.