194 citations · 1.9k across the 115 of their papers we have counts for
6 papers · 1 filter
Two-way finite automata with quantum and classical states
Andris Ambainis, John Watrous
We introduce 2-way finite automata with quantum and classical states (2qcfa's). This is a variant on the 2-way quantum finite automata (2qfa) model which may be simpler to implemen…
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…
Probabilistic Inductive Inference:a Survey
Andris Ambainis
Inductive inference is a recursion-theoretic theory of learning, first developed by E. M. Gold (1967). This paper surveys developments in probabilistic inductive inference. We main…
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…