194 citations · 1.9k across the 115 of their papers we have counts for
4 papers · 2 filters
Understanding Quantum Algorithms via Query Complexity
Andris Ambainis
Query complexity is a model of computation in which we have to compute a function of variables which can be accessed via queries. The complexity of an a…
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
Andris Ambainis, Martins Kokainis
We study quantum algorithms on search trees of unknown structure, in a model where the tree can be discovered by local exploration. That is, we are given the root of the tree and a…
Strong supremacy of quantum systems as communication resource
Maria Quadeer, Manik Banik, Andris Ambainis +1
We investigate the task of -level random access codes (-RACs) and consider the possibility of encoding classical strings of -level symbols (dits) into a quantum system of…
Optimal one-shot quantum algorithm for EQUALITY and AND
Andris Ambainis, Janis Iraids
We study the computation complexity of Boolean functions in the quantum black box model. In this model our task is to compute a function on an input $x\in\{0,…