194 citations · 1.9k across the 115 of their papers we have counts for
Showing 1998Show all
3 papers · 1 filter
quant-ph1998★ 1 cited
A note on quantum black-box complexity of almost all Boolean functions
Andris Ambainis
We show that, for almost all N-variable Boolean functions f, at least N/4-O(\sqrt{N} log N) queries are required to compute f in quantum black-box model with bounded error.
quant-ph1998★ 3 cited
Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma +1
We consider the possibility of encoding m classical bits into much fewer n quantum bits so that an arbitrary bit from the original m bits can be recovered with a good probability,…
quant-ph1998★ 35 cited
1-way quantum finite automata: strengths, weaknesses and generalizations
A. Ambainis, R. Freivalds
We study 1-way quantum finite automata (QFAs). First, we compare them with their classical counterparts. We show that, if an automaton is required to give the correct answer with a…