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

arXiv:2212.14433 · Lobachevskii Journal of Mathematics

Quantum Algorithm for Dynamic Programming Approach for DAGs and Applications

Kamil Ravilevich Khadiev, Liliya Safina

Published Feb 1, 2023• 3 citations
arXivHTMLPDF

Abstract

In this paper, we present a quantum algorithm for the dynamic programming approach for problems on directed acyclic graphs (DAGs). The running time of the algorithm is $$O(\sqrt{\hat{n}m}\log\hat{n})$$ , and the running time of the best known deterministic algorithm is $$O(n+m)$$ , where $$n$$ is the number of vertices, $$\hat{n}$$ is the number of vertices with at least one outgoing edge; $$m$$ is the number of edges. We show that we can solve problems that use OR, AND, NAND, MAX, and MIN functions as the main transition steps. The approach is useful for a couple of problems. One of them is computing a Boolean formula that is represented by Zhegalkin polynomial, a Boolean circuit with shared input and non-constant depth evaluation. Another two are the single source longest paths search for weighted DAGs and the diameter search problem for unweighted DAGs.

DOI
10.1134/s1995080223020191

Related papers

Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs

Kamil Ravilevich Khadiev, Liliya Safina

In this paper, we present a quantum algorithm for dynamic programming approach for problems on directed acyclic graphs (DAGs). The running time of the algorithm is $O(\sqrt{\hat{n}m}\log \hat{n})$, and the running time of the best known deterministic algorithm is $O(n+m)$, where $n$ is the number of vertices, $\hat{n}$ is the number of vertices with at least one outgoing edge; $m$ is the number of edges. We show that we can solve problems that use OR, AND, NAND, MAX and MIN functions as the main transition steps. The approach is useful for a couple of problems. One of them is computing a Boolean formula that is represented by Zhegalkin polynomial, a Boolean circuit with shared input and non-constant depth evaluating. Another two are the single source longest paths search for weighted DAGs and the diameter search problem for unweighted DAGs.

arXiv:1804.09950•Apr 26, 2018•1 citation

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).

Moscow University Computational Mathematics and Cybernetics•Jan 1, 2019•4 citations

Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms

Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista +2 more

We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem $\mathcal P$ and an instance $I$ of $\mathcal P$, such a speedup can be expressed in terms of the average degree $δ$ of the dependency digraph $G_{\mathcal{P}}(I)$ of $I$, determined by a recursive formulation of $\mathcal P$. The nodes of this graph are the subproblems of $\mathcal P$ induced by $I$ and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in $\tilde{O}(|V(G_{\mathcal{P}}(I))| \sqrtδ)$ time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted $n$-vertex digraph with $m$ edges that runs in $\tilde{O}(n\sqrt{nm})$ time, which improves the best known classical upper bound when $m \in Ω(n^{1.4})$.

arXiv:2507.00823•Jul 1, 2025•0 citations

Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms

Caroppo, Susanna, Da Lozzo, Giordano, Giuseppe Di Battista +2 more

We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem P and an instance I of P, such a speedup can be expressed in terms of the average degree δ of the dependency digraph GP(I) of I, determined by a recursive formulation of P. The nodes of this graph are the subproblems of P induced by I and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in Õ(|V (GP(I))|√δ) time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted n-vertex digraph with m edges that runs in Õ(n√nm) time, which improves the best known classical upper bound when m ∈ Ω(n1.4).

•Jan 1, 2025•0 citations

Quantum Algorithms for Solving Dynamic Programming Problems

Pooya Ronagh

We present a general quantum algorithm for solving finite-horizon dynamic programming problems. Up to polylogarithmic factors, our algorithm provides a quadratic quantum advantage in terms of the number of states of a given dynamic programming problem. This speedup comes at the expense of the appearance of other polynomial factors representative of the number of actions of the dynamic programming problem, the maximum value of the instantaneous reward, and the time horizon of the problem. Our algorithm can be applied to combinatorial optimization problems solved classically using dynamic programming techniques. As one application, we show that the travelling salesperson problem can be solved in $O^*(\lceil c \rceil^4 \sqrt{2^n})$ on a quantum computer, where $n$ is the number of vertices of the underlying graph and $\lceil c \rceil$ is its maximum edge-weight. As another example, we show that the minimum set-cover problem can be solved in $O(\sqrt{2^n} \operatorname{poly}(m, n))$, where $m$ is the number of sets used to cover a universe of size $n$. Finally, we prove lower bounds for the query complexity of quantum algorithms and classical randomized algorithms for solving dynamic programming problems, and show that no greater-than-quadratic speedup in either the number of states or number of actions can be achieved for solving dynamic programming problems using quantum algorithms.

•Jun 5, 2019•13 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.

arXiv:2408.10427•Aug 19, 2024•1 citation
In this paper, we present a quantum algorithm for the dynamic programming approach for problems on directed acyclic graphs (DAGs). The running time of the algorithm is O(n^mlog⁡n^)O(\sqrt{\hat{n}m}\log\hat{n})O(n^m​logn^) , and the running time of the best known deterministic algorithm is O(n+m)O(n+m)O(n+m) , where nnn is the number of vertices, n^\hat{n}n^ is the number of vertices with at least one outgoing edge; mmm is the number of edges. We show that we can solve problems that use OR, AND, NAND, MAX, and MIN functions as the main transition steps. The approach is useful for a couple of problems. One of them is computing a Boolean formula that is represented by Zhegalkin polynomial, a Boolean circuit with shared input and non-constant depth evaluation. Another two are the single source longest paths search for weighted DAGs and the diameter search problem for unweighted DAGs.
In this paper, we present a quantum algorithm for dynamic programming approach for problems on directed acyclic graphs (DAGs). The running time of the algorithm is O(n^mlog⁡n^)O(\sqrt{\hat{n}m}\log \hat{n})O(n^m​logn^), and the running time of the best known deterministic algorithm is O(n+m)O(n+m)O(n+m), where nnn is the number of vertices, n^\hat{n}n^ is the number of vertices with at least one outgoing edge; mmm is the number of edges. We show that we can solve problems that use OR, AND, NAND, MAX and MIN functions as the main transition steps. The approach is useful for a couple of problems. One of them is computing a Boolean formula that is represented by Zhegalkin polynomial, a Boolean circuit with shared input and non-constant depth evaluating. Another two are the single source longest paths search for weighted DAGs and the diameter search problem for unweighted DAGs.
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(nm log⁡  n)O(\sqrt {nm} \,\log \;n)O(nm​logn) 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(nm (log⁡  n)2)O(\sqrt {nm} \,{(\log \;n)^2})O(nm​(logn)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).
We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem P\mathcal PP and an instance III of P\mathcal PP, such a speedup can be expressed in terms of the average degree δδδ of the dependency digraph GP(I)G_{\mathcal{P}}(I)GP​(I) of III, determined by a recursive formulation of P\mathcal PP. The nodes of this graph are the subproblems of P\mathcal PP induced by III and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in O~(∣V(GP(I))∣δ)\tilde{O}(|V(G_{\mathcal{P}}(I))| \sqrtδ)O~(∣V(GP​(I))∣δ​) time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted nnn-vertex digraph with mmm edges that runs in O~(nnm)\tilde{O}(n\sqrt{nm})O~(nnm​) time, which improves the best known classical upper bound when m∈Ω(n1.4)m \in Ω(n^{1.4})m∈Ω(n1.4).
We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem P and an instance I of P, such a speedup can be expressed in terms of the average degree δ of the dependency digraph GP(I) of I, determined by a recursive formulation of P. The nodes of this graph are the subproblems of P induced by I and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in Õ(|V (GP(I))|√δ) time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted n-vertex digraph with m edges that runs in Õ(n√nm) time, which improves the best known classical upper bound when m ∈ Ω(n1.4).
We present a general quantum algorithm for solving finite-horizon dynamic programming problems. Up to polylogarithmic factors, our algorithm provides a quadratic quantum advantage in terms of the number of states of a given dynamic programming problem. This speedup comes at the expense of the appearance of other polynomial factors representative of the number of actions of the dynamic programming problem, the maximum value of the instantaneous reward, and the time horizon of the problem. Our algorithm can be applied to combinatorial optimization problems solved classically using dynamic programming techniques. As one application, we show that the travelling salesperson problem can be solved in O∗(⌈c⌉42n)O^*(\lceil c \rceil^4 \sqrt{2^n})O∗(⌈c⌉42n​) on a quantum computer, where nnn is the number of vertices of the underlying graph and ⌈c⌉\lceil c \rceil⌈c⌉ is its maximum edge-weight. As another example, we show that the minimum set-cover problem can be solved in O(2npoly⁡(m,n))O(\sqrt{2^n} \operatorname{poly}(m, n))O(2n​poly(m,n)), where mmm is the number of sets used to cover a universe of size nnn. Finally, we prove lower bounds for the query complexity of quantum algorithms and classical randomized algorithms for solving dynamic programming problems, and show that no greater-than-quadratic speedup in either the number of states or number of actions can be achieved for solving dynamic programming problems using quantum algorithms.
Given an undirected, weighted graph, with nnn vertices and mmm edges, and two special vertices sss and ttt, 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 O~(l2m)\tilde{O}(l^2\sqrt{m})O~(l2m​) expected time and uses O(log⁡n)O(\log{n})O(logn) space on graphs where the shortest sss-ttt path is also a minimum resistance sss-ttt 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.537q>0.537q>0.537 of finding the shortest sss-ttt path. In such cases the quantum algorithm outputs the shortest sss-ttt path with high probability in O~(ℓm)\widetilde{O}(\ell\sqrt{m})O(ℓm​) expected time and O(log⁡n)O(\log{n})O(logn) space, where lll is the length (or total weight, in case of weighted graphs) of the shortest sss-ttt path. This algorithm can be parallelised to O~(lm)\tilde{O}(\sqrt{lm})O~(lm​) circuit depth when using O(llog⁡n)O(l\log{n})O(llogn) 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.