194 citations · 1.9k across the 115 of their papers we have counts for
6 papers · 2 filters
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality
Scott Aaronson, Andris Ambainis, Jānis Iraids +2
We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function is computable by a 1-query quantum alg…
Quantum Advantages in (n,d)->1 Random Access Codes
Andris Ambainis, Dmitry Kravchenko, Sk Sazim +2
A random access code (RAC), corresponding to a communication primitive with various applications in quantum information theory, is an instance of a preparation-and-measurement scen…
Spatial search by quantum walk is optimal for almost all graphs
Shantanav Chakraborty, Leonardo Novo, Andris Ambainis +1
The problem of finding a marked node in a graph can be solved by the spatial search algorithm based on continuous-time quantum walks (CTQW). However, this algorithm is known to run…
Limited preparation contextuality in quantum theory and its relation to the Cirel'son bound
Manik Banik, Some Sankar Bhattacharya, Amit Mukherjee +3
Kochen-Specker (KS) theorem lies at the heart of the foundations of quantum mechanics. It establishes impossibility of explaining predictions of quantum theory by any noncontextual…
Correcting for Potential Barriers in Quantum Walk Search
Andris Ambainis, Thomas G. Wong
A randomly walking quantum particle searches in Grover's iterations for a marked vertex on the complete graph of vertices by repeatedly querying an oracle that fl…
Quantum Search with Multiple Walk Steps per Oracle Query
Thomas G. Wong, Andris Ambainis
We identify a key difference between quantum search by discrete- and continuous-time quantum walks: a discrete-time walk typically performs one walk step per oracle query, whereas…