10 citations · 12 across the 3 of their papers we have counts for
3 papers · 1 filter
Quantum speedups for treewidth
Vladislavs Kļevickis, Krišjānis Prūsis, Jevgēnijs Vihrovs
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 (Co…
Quantum speedups for dynamic programming on -dimensional lattice graphs
Adam Glos, Martins Kokainis, Ryuhei Mori +1
Motivated by the quantum speedup for dynamic programming on the Boolean hypercube by Ambainis et al. (2019), we investigate which graphs admit a similar quantum advantage. In this…
Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
Andris Ambainis, Kaspars Balodis, Jānis Iraids +3
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 i…