65 citations · 120 across the 10 of their papers we have counts for
4 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…
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…
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…