194 citations · 1.9k across the 115 of their papers we have counts for
3 papers · 2 filters
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,…
Worst case analysis of non-local games
Andris Ambainis, Arturs Backurs, Kaspars Balodis +3
Non-local games are studied in quantum information because they provide a simple way for proving the difference between the classical world and the quantum world. A non-local game…