65 citations · 154 across the 13 of their papers we have counts for
Showing 1999 · quant-phShow all
2 papers · 2 filters
quant-ph1999
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…
quant-ph1999
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…