3 papers
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…
cs.CC2025
Boolean Functions with Minimal Spectral Sensitivity
KriÅ¡jÄnis PrÅ«sis, JevgÄnijs Vihrovs
We show examples of total Boolean functions that depend on variables and have spectral sensitivity , which is asymptotically minimal. Our main new function c…