194 citations · 1.9k across the 115 of their papers we have counts for
4 papers · 2 filters
Quantum finite multitape automata
Andris Ambainis, Richard Bonner, Rusins Freivalds +2
Quantum finite automata were introduced by C.Moore, J.P. Crutchfield, and by A.Kondacs and J.Watrous. This notion is not a generalization of the deterministic finite automata. More…
Probabilities to accept languages by quantum finite automata
Andris Ambainis, Richard Bonner, Rusins Freivalds +1
We construct a hierarchy of regular languages such that the current language in the hierarchy can be accepted by 1-way quantum finite automata with a probability smaller than the c…
Average-Case Quantum Query Complexity
Andris Ambainis, Ronald de Wolf
We compare classical and quantum query complexities of total Boolean functions. It is known that for worst-case complexity, the gap between quantum and classical can be at most pol…
A better lower bound for quantum algorithms searching an ordered list
Andris Ambainis
We show that any quantum algorithm searching an ordered list of n elements needs to examine at least 1/12 log n-O(1) of them. Classically, log n queries are both necessary and suff…