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:2202.08186 · Leibniz international proceedings in informatics

Quantum Speedups for Treewidth

Vladislavs Kļevickis, Krišjānis Prūsis, Jevgēnijs Vihrovs

Published Jan 1, 2022• 2 citations
arXivHTMLPDF

Abstract

In this paper, we study quantum algorithms for computing the exact value of the treewidth of a graph. Our algorithms are based on the classical algorithm by Fomin and Villanger (Combinatorica 32, 2012) that uses O(2.616ⁿ) time and polynomial space. We show three quantum algorithms with the following complexity, using QRAM in both exponential space algorithms: - O(1.618ⁿ) time and polynomial space; - O(1.554ⁿ) time and O(1.452ⁿ) space; - O(1.538ⁿ) time and space. In contrast, the fastest known classical algorithm for treewidth uses O(1.755ⁿ) time and space. The first two speed-ups are obtained in a fairly straightforward way. The first version uses additionally only Grover’s search and provides a quadratic speedup. The second speedup is more time-efficient and uses both Grover’s search and the quantum exponential dynamic programming by Ambainis et al. (SODA '19). The third version uses the specific properties of the classical algorithm and treewidth, with a modified version of the quantum dynamic programming on the hypercube. As a small side result, we give a new classical time-space tradeoff for computing treewidth in O^*(2ⁿ) time and O^*(√{2ⁿ}) space.

DOI
10.4230/lipics.tqc.2022.11

Related papers

Exponential-Time Quantum Algorithms for Graph Coloring Problems

Kazuya Shimizu, Ryuhei Mori

Abstract The fastest known classical algorithm deciding the k-colorability of n-vertex graph requires running time $$\varOmega (2^n)$$ Ω ( 2 n ) for $$k\ge 5$$ k ≥ 5 . In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time $$O(1.9140^n)$$ O ( 1 . 9140 n ) using quantum random access memory (QRAM). Our approach is based on Ambainis et al’s quantum dynamic programming with applications of Grover’s search to branching algorithms. We also present a polynomial-space quantum algorithm not using QRAM for the graph 20-coloring problem with running time $$O(1.9575^n)$$ O ( 1 . 9575 n ) . For the polynomial-space quantum algorithm, we essentially develop $$(4-\epsilon )^n$$ ( 4 - ϵ ) n -time classical algorithms that can be improved quadratically by Grover’s search.

Algorithmica•Jun 1, 2022•18 citations

Quantum Time-Space Tradeoffs for Exponential Dynamic Programming

Susanna Caroppo, Jevgēnijs Vihrovs, Dārta Zajakina +1 more

We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While giving provable complexity speedups and applicable to a variety of NP-hard problems, these algorithms have a notable drawback: they require a large amount of Quantum Random Access Memory (QRAM), which potentially could be very challenging to implement in a physical quantum computer. In this work, we study how we can improve the space complexity by trading it for time, while still retaining a speedup over the classical algorithms. We show novel quantum time-space tradeoffs by combining different classical approaches with quantum techniques. For instance, we show that the Travelling Salesman Problem can be solved quantumly in $\widetilde O(1.859^n)$ time and $\widetilde O(1.315^n)$ QRAM space.

quant-pharXiv:2604.02233•Leibniz international proceedings in informatics•Apr 3, 2026•0 citations

Exponential-time quantum algorithms for graph coloring problems

Shimizu, Kazuya, Ryuhei Mori

The fastest known classical algorithm deciding the $k$-colorability of $n$-vertex graph requires running time $Ω(2^n)$ for $k\ge 5$. In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time $O(1.9140^n)$ using quantum random access memory (QRAM). Our approach is based on Ambainis et al's quantum dynamic programming with applications of Grover's search to branching algorithms. We also present a polynomial-space quantum algorithm not using QRAM for the graph $20$-coloring problem with running time $O(1.9575^n)$. In the polynomial-space quantum algorithm, we essentially show $(4-ε)^n$-time classical algorithms that can be improved quadratically by Grover's search.

arXiv:1907.00529•Jul 1, 2019•0 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 Exponential-Time Dynamic Programming Algorithms

Andris Ambainis, Kaspars Balodis, Jānis Iraids +3 more

In this paper we study quantum algorithms for NP-complete problems whose best classical algorithm is an exponential time application of dynamic programming. We introduce the path in the hypercube problem that models many of these dynamic programming algorithms. In this problem we are asked whether there is a path from $0^n$ to $1^n$ in a given subgraph of the Boolean hypercube, where the edges are all directed from smaller to larger Hamming weight. We give a quantum algorithm that solves path in the hypercube in time $O^*(1.817^n)$. The technique combines Grover's search with computing a partial dynamic programming table. We use this approach to solve a variety of vertex ordering problems on graphs in the same time $O^*(1.817^n)$, and graph bandwidth in time $O^*(2.946^n)$. Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time $O^*(1.728^n)$.

arXiv:1807.05209•Jul 13, 2018•1 citation

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
In this paper, we study quantum algorithms for computing the exact value of the treewidth of a graph. Our algorithms are based on the classical algorithm by Fomin and Villanger (Combinatorica 32, 2012) that uses O(2.616ⁿ) time and polynomial space. We show three quantum algorithms with the following complexity, using QRAM in both exponential space algorithms: - O(1.618ⁿ) time and polynomial space; - O(1.554ⁿ) time and O(1.452ⁿ) space; - O(1.538ⁿ) time and space. In contrast, the fastest known classical algorithm for treewidth uses O(1.755ⁿ) time and space. The first two speed-ups are obtained in a fairly straightforward way. The first version uses additionally only Grover’s search and provides a quadratic speedup. The second speedup is more time-efficient and uses both Grover’s search and the quantum exponential dynamic programming by Ambainis et al. (SODA '19). The third version uses the specific properties of the classical algorithm and treewidth, with a modified version of the quantum dynamic programming on the hypercube. As a small side result, we give a new classical time-space tradeoff for computing treewidth in O^(2ⁿ) time and O^(√{2ⁿ}) space.
Abstract The fastest known classical algorithm deciding the k-colorability of n-vertex graph requires running time Ω(2n)\varOmega (2^n)Ω(2n) Ω ( 2 n ) for k≥5k\ge 5k≥5 k ≥ 5 . In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time O(1.9140n)O(1.9140^n)O(1.9140n) O ( 1 . 9140 n ) using quantum random access memory (QRAM). Our approach is based on Ambainis et al’s quantum dynamic programming with applications of Grover’s search to branching algorithms. We also present a polynomial-space quantum algorithm not using QRAM for the graph 20-coloring problem with running time O(1.9575n)O(1.9575^n)O(1.9575n) O ( 1 . 9575 n ) . For the polynomial-space quantum algorithm, we essentially develop (4−ϵ)n(4-\epsilon )^n(4−ϵ)n ( 4 - ϵ ) n -time classical algorithms that can be improved quadratically by Grover’s search.
We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While giving provable complexity speedups and applicable to a variety of NP-hard problems, these algorithms have a notable drawback: they require a large amount of Quantum Random Access Memory (QRAM), which potentially could be very challenging to implement in a physical quantum computer. In this work, we study how we can improve the space complexity by trading it for time, while still retaining a speedup over the classical algorithms. We show novel quantum time-space tradeoffs by combining different classical approaches with quantum techniques. For instance, we show that the Travelling Salesman Problem can be solved quantumly in O~(1.859n)\widetilde O(1.859^n)O(1.859n) time and O~(1.315n)\widetilde O(1.315^n)O(1.315n) QRAM space.
The fastest known classical algorithm deciding the kkk-colorability of nnn-vertex graph requires running time Ω(2n)Ω(2^n)Ω(2n) for k≥5k\ge 5k≥5. In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time O(1.9140n)O(1.9140^n)O(1.9140n) using quantum random access memory (QRAM). Our approach is based on Ambainis et al's quantum dynamic programming with applications of Grover's search to branching algorithms. We also present a polynomial-space quantum algorithm not using QRAM for the graph 202020-coloring problem with running time O(1.9575n)O(1.9575^n)O(1.9575n). In the polynomial-space quantum algorithm, we essentially show (4−ε)n(4-ε)^n(4−ε)n-time classical algorithms that can be improved quadratically by Grover's search.
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).
In this paper we study quantum algorithms for NP-complete problems whose best classical algorithm is an exponential time application of dynamic programming. We introduce the path in the hypercube problem that models many of these dynamic programming algorithms. In this problem we are asked whether there is a path from 0n0^n0n to 1n1^n1n in a given subgraph of the Boolean hypercube, where the edges are all directed from smaller to larger Hamming weight. We give a quantum algorithm that solves path in the hypercube in time O∗(1.817n)O^*(1.817^n)O∗(1.817n). The technique combines Grover's search with computing a partial dynamic programming table. We use this approach to solve a variety of vertex ordering problems on graphs in the same time O∗(1.817n)O^*(1.817^n)O∗(1.817n), and graph bandwidth in time O∗(2.946n)O^*(2.946^n)O∗(2.946n). Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time O∗(1.728n)O^*(1.728^n)O∗(1.728n).
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).