IEEE Transactions on Quantum Engineering

Solving the Network Shortest Path Problem on a Quantum Annealer

Thomas Krauss, Joey McCollum

Published Jan 1, 2020• 34 citations

Abstract

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.

DOI: 10.1109/tqe.2020.3021921

Related papers

Solving the Max-Flow Problem on a Quantum Annealing Computer

Thomas Krauss, Joey McCollum, Chapman Pendery +2 more

IEEE Transactions on Quantum EngineeringJan 1, 202030 citations

QUBO Formulation of the Shortest Path Algorithm and its Evaluation on a Quantum Annealer

Renáta Rusnáková, Martin Chovanec, Maroš Harahus +1 more

IEEE World Symposium on Applied Machine Intelligence and Informatics (SAMI)Jan 23, 20250 citations

Advances in quantum algorithms for the shortest path problem

Adam Wesołowski, Stephen Piddock

arXiv:2408.10427Aug 19, 20241 citation

The Steiner Tree Problem: Novel QUBO Formulation and Quantum Annealing Implementation

Dan Li, Xiang-Hui Wu, Ji-Rong Liu

quant-pharXiv:2603.04089Mar 5, 20260 citations

A Review of Quantum Algorithms for the Unconstrained Shortest Path Problem

Theodorakopoulos, Panagiotis, Ani Anciaux‐Sedrakian, Ibtihel Ben Gharbia +3 more

Apr 24, 20260 citations

Quantum Algorithm for Shortest Path Search in Directed Acyclic Graph

Kamil Ravilevich Khadiev, Liliya Safina

Moscow University Computational Mathematics and CyberneticsJan 1, 20194 citations

IEEE Transactions on Quantum Engineering

Solving the Network Shortest Path Problem on a Quantum Annealer

Thomas Krauss, Joey McCollum

Published Jan 1, 2020• 34 citations

Publisher

Abstract

DOI: 10.1109/tqe.2020.3021921

Related papers

Solving the Max-Flow Problem on a Quantum Annealing Computer

Thomas Krauss, Joey McCollum, Chapman Pendery +2 more

This article addresses the question of implementing a maximum flow algorithm on directed graphs in a formulation suitable for a quantum annealing computer. Three distinct approaches are presented. In all three cases, the flow problem is formulated as a quadratic unconstrained binary optimization (QUBO) problem amenable to quantum annealing. The first implementation augments a graph with integral edge capacities into a multigraph with unit-capacity edges and encodes the fundamental objective and constraints of the maximum flow problem using a number of qubits equal to the total capacity of the graph $\sum _i{c_i}$ . The second implementation, which encodes flows through edges using a binary representation, reduces the required number of qubits to $\mathcal {O}(|E| \log C_{\max })$ , where $|E|$ and $C_{\max }$ denote the number of edges and maximum edge capacity of the graph, respectively. The third implementation adapts the dual minimum cut formulation and encodes the problem instance using $|V|$ qubits, where $|V|$ is the number of vertices in the graph. Scaling factors for penalty terms and coupling matrix construction times are made explicit in this article.This article addresses the question of implementing a maximum flow algorithm on directed graphs in a formulation suitable for a quantum annealing computer. Three distinct approaches are presented. In all three cases, the flow problem is formulated as a quadratic unconstrained binary optimization (QUBO) problem amenable to quantum annealing. The first implementation augments a graph with integral edge capacities into a multigraph with unit-capacity edges and encodes the fundamental objective and constraints of the maximum flow problem using a number of qubits equal to the total capacity of the graph $\sum _i{c_i}$. The second implementation, which encodes flows through edges using a binary representation, reduces the required number of qubits to $\mathcal {O}(|E| \log C_{\max })$, where $|E|$ and $C_{\max }$ denote the number of edges and maximum edge capacity of the graph, respectively. The third implementation adapts the dual minimum cut formulation and encodes the problem instance using $|V|$ qubits, where $|V|$ is the number of vertices in the graph. Scaling factors for penalty terms and coupling matrix construction times are made explicit in this article.

IEEE Transactions on Quantum EngineeringJan 1, 202030 citations

QUBO Formulation of the Shortest Path Algorithm and its Evaluation on a Quantum Annealer

Renáta Rusnáková, Martin Chovanec, Maroš Harahus +1 more

This study focuses on reformulating the shortest path problem in undirected weighted graphs into a QUBO problem, leveraging the D-Wave quantum annealing hybrid solver for execution. While A * search with heuristics, a widely used algorithm for solving shortest path problem, serves as a baseline for comparison, our primary contribution lies in analyzing the accuracy and benefits of the proposed QUBO formulation. Our analysis reveals that the proposed QUBO formulation together with selected quantum annealing hybrid solver is loosing its efficiency with increasing number of nodes. This is caused by the size of the problem and related penalty calculation but also by the architecture of the D-Wave QPU and design of the hybrid solver. We are proposing techniques to improve the results, such as graph pruning during preprocessing or penalty parameter tuning to achieve better, more accurate, results. This study provides valuable insights into the limitations of current approaches and explores the future applications of quantum computing in solving real-world challenges.This study focuses on reformulating the shortest path problem in undirected weighted graphs into a QUBO problem, leveraging the D-Wave quantum annealing hybrid solver for execution. While A * search with heuristics, a widely used algorithm for solving shortest path problem, serves as a baseline for comparison, our primary contribution lies in analyzing the accuracy and benefits of the proposed QUBO formulation. Our analysis reveals that the proposed QUBO formulation together with selected quantum annealing hybrid solver is loosing its efficiency with increasing number of nodes. This is caused by the size of the problem and related penalty calculation but also by the architecture of the D-Wave QPU and design of the hybrid solver. We are proposing techniques to improve the results, such as graph pruning during preprocessing or penalty parameter tuning to achieve better, more accurate, results. This study provides valuable insights into the limitations of current approaches and explores the future applications of quantum computing in solving real-world challenges.

IEEE World Symposium on Applied Machine Intelligence and Informatics (SAMI)Jan 23, 20250 citations

Advances in quantum algorithms for the shortest path problem

Adam Wesołowski, Stephen Piddock

Given an undirected, weighted graph, with $n$ vertices and $m$ edges, and two special vertices $s$ and $t$ , the problem is to find the shortest path between them. We give two bounded-error quantum algorithms with improved runtime in the adjacency list model that solve the problem on special classes of graphs defined via pathfinding probabilities of classical random walks and the electrical network framework. Firstly, we give a simple quantum algorithm based on sampling edges from a graph via the quantum flow state and running a classical algorithm on the sampled edges. It runs in $\tilde{O}(l^2\sqrt{m})$ expected time and uses $O(\log{n})$ space on graphs where the shortest $s$ - $t$ path is also a minimum resistance $s$ - $t$ subgraph. Our main algorithm can be thought of as a divide and conquer version of this approach and works on a special class of graphs where classical loop-erased random walk has a probability $q>0.537$ of finding the shortest $s$ - $t$ path. In such cases the quantum algorithm outputs the shortest $s$ - $t$ path with high probability in $\widetilde{O}(\ell\sqrt{m})$ expected time and $O(\log{n})$ space, where $l$ is the length (or total weight, in case of weighted graphs) of the shortest $s$ - $t$ path. This algorithm can be parallelised to $\tilde{O}(\sqrt{lm})$ circuit depth when using $O(l\log{n})$ space. With the latter we partially resolve with an affirmative answer the open problem of whether a path between two vertices can be found in the number of steps required to detect it.Given an undirected, weighted graph, with $n$ vertices and $m$ edges, and two special vertices $s$ and $t$, the problem is to find the shortest path between them. We give two bounded-error quantum algorithms with improved runtime in the adjacency list model that solve the problem on special classes of graphs defined via pathfinding probabilities of classical random walks and the electrical network framework. Firstly, we give a simple quantum algorithm based on sampling edges from a graph via the quantum flow state and running a classical algorithm on the sampled edges. It runs in $\tilde{O}(l^2\sqrt{m})$ expected time and uses $O(\log{n})$ space on graphs where the shortest $s$-$t$ path is also a minimum resistance $s$-$t$ subgraph. Our main algorithm can be thought of as a divide and conquer version of this approach and works on a special class of graphs where classical loop-erased random walk has a probability $q>0.537$ of finding the shortest $s$-$t$ path. In such cases the quantum algorithm outputs the shortest $s$-$t$ path with high probability in $\widetilde{O}(\ell\sqrt{m})$ expected time and $O(\log{n})$ space, where $l$ is the length (or total weight, in case of weighted graphs) of the shortest $s$-$t$ path. This algorithm can be parallelised to $\tilde{O}(\sqrt{lm})$ circuit depth when using $O(l\log{n})$ space. With the latter we partially resolve with an affirmative answer the open problem of whether a path between two vertices can be found in the number of steps required to detect it.

arXiv:2408.10427Aug 19, 20241 citation

The Steiner Tree Problem: Novel QUBO Formulation and Quantum Annealing Implementation

Dan Li, Xiang-Hui Wu, Ji-Rong Liu

The Steiner Tree Problem (STP) is a well-known NP-hard combinatorial optimization problem, which has wide applications in network design, integrated circuit layout, bioinformatics, and other fields. However, traditional algorithms often struggle to balance efficiency and solution quality when dealing with large-scale STP instances. In this paper, we propose a new quantum annealing-based algorithm for solving the STP: we first model the STP into a quadratic unconstrained binary optimization (QUBO) form suitable for quantum annealing, then design a corresponding encoding strategy, and finally verify the algorithm through experimental tests. The results show that our quantum annealing-based method can obtain high-quality solutions with relatively low computational overhead for moderate-scale STP instances, providing a new feasible path for handling this intractable combinatorial optimization problem.The Steiner Tree Problem (STP) is a well-known NP-hard combinatorial optimization problem, which has wide applications in network design, integrated circuit layout, bioinformatics, and other fields. However, traditional algorithms often struggle to balance efficiency and solution quality when dealing with large-scale STP instances. In this paper, we propose a new quantum annealing-based algorithm for solving the STP: we first model the STP into a quadratic unconstrained binary optimization (QUBO) form suitable for quantum annealing, then design a corresponding encoding strategy, and finally verify the algorithm through experimental tests. The results show that our quantum annealing-based method can obtain high-quality solutions with relatively low computational overhead for moderate-scale STP instances, providing a new feasible path for handling this intractable combinatorial optimization problem.

quant-pharXiv:2603.04089Mar 5, 20260 citations

A Review of Quantum Algorithms for the Unconstrained Shortest Path Problem

Theodorakopoulos, Panagiotis, Ani Anciaux‐Sedrakian, Ibtihel Ben Gharbia +3 more

We investigate the relevance of variational algorithms for the single-source single-destination shortest path problem, within the application framework of eco-routing. The problem is formulated via a Quadratic Unconstrained Binary Optimization (QUBO) model, which is solved using VQE and QAOA algorithms. For QAOA two different initialization schemes are tested, based on a heuristic strategy, whereas for VQE we test two different ansatzes. The results highlight both the feasibility and scalability issues of solving the shortest path problem with quantum optimization approaches, while providing a simple yet interesting comparison between VQE and QAOA. This work aims to establish an initial direction towards addressing more challenging constrained variants of the problem.We investigate the relevance of variational algorithms for the single-source single-destination shortest path problem, within the application framework of eco-routing. The problem is formulated via a Quadratic Unconstrained Binary Optimization (QUBO) model, which is solved using VQE and QAOA algorithms. For QAOA two different initialization schemes are tested, based on a heuristic strategy, whereas for VQE we test two different ansatzes. The results highlight both the feasibility and scalability issues of solving the shortest path problem with quantum optimization approaches, while providing a simple yet interesting comparison between VQE and QAOA. This work aims to establish an initial direction towards addressing more challenging constrained variants of the problem.

Apr 24, 20260 citations

Quantum Algorithm for Shortest Path Search in Directed Acyclic Graph

Kamil Ravilevich Khadiev, Liliya Safina

In this work, we consider a well-known “Single Source Shortest Path Search” problems for weighted directed acyclic graphs (DAGs). We suggest a quantum algorithm with time complexity $O(\sqrt {nm} \,\log \;n)$ and O(1/n) error probability, where n is a number of Vertexes, m is the number of edges. We use quantum dynamic programming approach (Khadiev, 2018) and Dürr and Høyer minimum search algorithm to speed up our search. Our algorithm is better than C. Dürr and coauthors’ quantum algorithm for an undirected graph. The time complexity of C. Dürr’s algorithm is $O(\sqrt {nm} \,{(\log \;n)^2})$ . The best known deterministic algorithm for the problem is based on a dynamic programming approach and its time complexity is O (n + m). At the same time, if we use algorithms for general graphs, then we do not get better results. The time complexity of best implementations of Dijkstra’s algorithm with Fibonacci heap is O (m + n log n).In this work, we consider a well-known “Single Source Shortest Path Search” problems for weighted directed acyclic graphs (DAGs). We suggest a quantum algorithm with time complexity $O(\sqrt {nm} \,\log \;n)$ and O(1/n) error probability, where n is a number of Vertexes, m is the number of edges. We use quantum dynamic programming approach (Khadiev, 2018) and Dürr and Høyer minimum search algorithm to speed up our search. Our algorithm is better than C. Dürr and coauthors’ quantum algorithm for an undirected graph. The time complexity of C. Dürr’s algorithm is $O(\sqrt {nm} \,{(\log \;n)^2})$ . The best known deterministic algorithm for the problem is based on a dynamic programming approach and its time complexity is O (n + m). At the same time, if we use algorithms for general graphs, then we do not get better results. The time complexity of best implementations of Dijkstra’s algorithm with Fibonacci heap is O (m + n log n).

Moscow University Computational Mathematics and CyberneticsJan 1, 20194 citations

\sum _i{c_i}

. The second implementation, which encodes flows through edges using a binary representation, reduces the required number of qubits to

\mathcal {O}(|E| \log C_{\max })

, where

|E|

and

C_{\max }

denote the number of edges and maximum edge capacity of the graph, respectively. The third implementation adapts the dual minimum cut formulation and encodes the problem instance using

|V|

qubits, where

|V|

is the number of vertices in the graph. Scaling factors for penalty terms and coupling matrix construction times are made explicit in this article.

Given an undirected, weighted graph, with

n

vertices and

m

edges, and two special vertices

s

and

t

, the problem is to find the shortest path between them. We give two bounded-error quantum algorithms with improved runtime in the adjacency list model that solve the problem on special classes of graphs defined via pathfinding probabilities of classical random walks and the electrical network framework. Firstly, we give a simple quantum algorithm based on sampling edges from a graph via the quantum flow state and running a classical algorithm on the sampled edges. It runs in

\tilde{O}(l^2\sqrt{m})

expected time and uses

O(\log{n})

space on graphs where the shortest

s

t

path is also a minimum resistance

s

t

subgraph. Our main algorithm can be thought of as a divide and conquer version of this approach and works on a special class of graphs where classical loop-erased random walk has a probability

q>0.537

of finding the shortest

s

t

path. In such cases the quantum algorithm outputs the shortest

s

t

path with high probability in

\widetilde{O}(\ell\sqrt{m})

expected time and

O(\log{n})

space, where

l

is the length (or total weight, in case of weighted graphs) of the shortest

s

t

path. This algorithm can be parallelised to

\tilde{O}(\sqrt{lm})

circuit depth when using

O(l\log{n})

space. With the latter we partially resolve with an affirmative answer the open problem of whether a path between two vertices can be found in the number of steps required to detect it.

In this work, we consider a well-known “Single Source Shortest Path Search” problems for weighted directed acyclic graphs (DAGs). We suggest a quantum algorithm with time complexity

O(\sqrt {nm} \,\log \;n)

and O(1/n) error probability, where n is a number of Vertexes, m is the number of edges. We use quantum dynamic programming approach (Khadiev, 2018) and Dürr and Høyer minimum search algorithm to speed up our search. Our algorithm is better than C. Dürr and coauthors’ quantum algorithm for an undirected graph. The time complexity of C. Dürr’s algorithm is

O(\sqrt {nm} \,{(\log \;n)^2})

. The best known deterministic algorithm for the problem is based on a dynamic programming approach and its time complexity is O (n + m). At the same time, if we use algorithms for general graphs, then we do not get better results. The time complexity of best implementations of Dijkstra’s algorithm with Fibonacci heap is O (m + n log n).