5 citations · 10 across the 3 of their papers we have counts for
3 papers
Parameterized Quantum Query Complexity of Graph Collision
Andris Ambainis, Kaspars Balodis, Jānis Iraids +2
We present three new quantum algorithms in the quantum query model for \textsc{graph-collision} problem: \begin{itemize} \item an algorithm based on tree decomposition that uses $O…
Search by quantum walks on two-dimensional grid without amplitude amplification
Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs +2
We study search by quantum walk on a finite two dimensional grid. The algorithm of Ambainis, Kempe, Rivosh (quant-ph/0402107) takes O(\sqrt{N log N}) steps and finds a marked locat…
Quantum strategies are better than classical in almost any XOR game
Andris Ambainis, Arturs Backurs, Kaspars Balodis +4
We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n,…