65 citations · 120 across the 10 of their papers we have counts for
Showing 1998Show all
2 papers · 1 filter
quant-ph1998
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
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…