3 papers
quant-ph2020
A random-walk benchmark for single-electron circuits
David Reifert, Martins Kokainis, Andris Ambainis +2
Mesoscopic integrated circuits achieving high-fidelity control of elementary quantum systems require new methodology for benchmarking. We offer circuit-level statistical descriptio…
quant-ph2019
Quadratic speedup for finding marked vertices by quantum walks
Andris Ambainis, András Gilyén, Stacey Jeffery +1
A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quan…
quant-ph2018
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…