Showing quant-phShow all
3 papers · 1 filter
quant-ph2026
Quantum Time-Space Tradeoffs for Exponential Dynamic Programming
Susanna Caroppo, JevgÄnijs Vihrovs, Jevgēnijs Vihrovs +3
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 problem…
quant-ph2025
Quantum Search on Computation Trees
JevgÄnijs Vihrovs
We show a simple generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC 2018) to the case where vertices can have different times of comput…
quant-ph2024
Quantum algorithms for Hopcroft's problem
Vladimirs Andrejevs, Aleksandrs Belovs, JevgÄnijs Vihrovs
In this work we study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. Given points and lines in the plane, the task is t…