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

The Journal of Supercomputing

Modeling of shortest path of a graph in quantum computing

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

Published Oct 14, 2025• 1 citation
Publisher
DOI
10.1007/s11227-025-07968-3

Related papers

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

Aniket Bembale, Nagendra Singh, P. Vinayaka +1 more

Lecture notes in networks and systems•Dec 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

Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model

Taisuke Izumi, François Le Gall

The All-Pairs Shortest Path problem (APSP) is one of the most central problems in distributed computation. In the CONGEST-CLIQUE model, in which n nodes communicate with each other over a fully connected network by exchanging messages of O(łog n) bits in synchronous rounds, the best known general algorithm for APSP uses Õ(n1/3) rounds. Breaking this barrier is a fundamental challenge in distributed graph algorithms. In this paper we investigate for the first time quantum distributed algorithms in the CONGEST-CLIQUE model, where nodes can exchange messages of O(log n) quantum bits, and show that this barrier can be broken: we construct a Õ(n1/4)-round quantum distributed algorithm for the APSP over directed graphs with polynomial weights in the CONGEST-CLIQUE model. This speedup in the quantum setting contrasts with the case of the standard CONGEST model, for which Elkin et al. (PODC 2014) showed that quantum communication does not offer significant advantages over classical communication.

arXiv:1906.02456•ACM Symposium on Principles of Distributed Computing (PODC)•Jul 16, 2019•23 citations

Evaluation on Quantum Computation and Classic Parallel Approaches for Finding Estimation of the Length of Shortest Path in a Weighted Graph

Mir Shahriar Emami, Mohammad Reza Fattahi, Hossein Keshmiri

In this paper we evaluate our presented Quantum Approach for finding the Estimation of the Length of the Shortest Path in a Connected Weighted Graph which is achieved with a polynomial time complexity about O(n) and as a result of evaluation we show that the Probability of Success of our presented Quantum Approach is increased if the Standard Deviation of the Length of all possible paths between Source and Target vertices is increased also we show that if the Standard Deviation is low nevertheless our Quantum Computation Approach is satisfactory and even the standard deviation is exactly zero the probability of Success of our Quantum Approach is not only zero but also is %100. Also we present a Classic Parallel Approach for finding the Estimation of the Length of the shortest path and then as a comparison between our Quantum Computation and Classic Parallel Approaches we show that even by applying the Classic Parallel Approach the problem can be solved with time complexity about O(log(2n -1)).

IEEE/ACIS International Conference on Computer and Information Science (ICIS)•May 1, 2008•0 citations

The Shortest Pathfinding by a Quantum Walk

Leo Matsuoka, Kenta Yuki, Hynek Lavička +1 more

The Japan Society of Applied Physics•Jul 6, 2021•0 citations
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.
The All-Pairs Shortest Path problem (APSP) is one of the most central problems in distributed computation. In the CONGEST-CLIQUE model, in which n nodes communicate with each other over a fully connected network by exchanging messages of O(łog n) bits in synchronous rounds, the best known general algorithm for APSP uses Õ(n1/3) rounds. Breaking this barrier is a fundamental challenge in distributed graph algorithms. In this paper we investigate for the first time quantum distributed algorithms in the CONGEST-CLIQUE model, where nodes can exchange messages of O(log n) quantum bits, and show that this barrier can be broken: we construct a Õ(n1/4)-round quantum distributed algorithm for the APSP over directed graphs with polynomial weights in the CONGEST-CLIQUE model. This speedup in the quantum setting contrasts with the case of the standard CONGEST model, for which Elkin et al. (PODC 2014) showed that quantum communication does not offer significant advantages over classical communication.
In this paper we evaluate our presented Quantum Approach for finding the Estimation of the Length of the Shortest Path in a Connected Weighted Graph which is achieved with a polynomial time complexity about O(n) and as a result of evaluation we show that the Probability of Success of our presented Quantum Approach is increased if the Standard Deviation of the Length of all possible paths between Source and Target vertices is increased also we show that if the Standard Deviation is low nevertheless our Quantum Computation Approach is satisfactory and even the standard deviation is exactly zero the probability of Success of our Quantum Approach is not only zero but also is %100. Also we present a Classic Parallel Approach for finding the Estimation of the Length of the shortest path and then as a comparison between our Quantum Computation and Classic Parallel Approaches we show that even by applying the Classic Parallel Approach the problem can be solved with time complexity about O(log(2n -1)).