0000000000033915
AUTHOR
Aija Berzina
showing 2 related works from this author
Ambainis-Freivalds’ Algorithm for Measure-Once Automata
2001
An algorithm given by Ambainis and Freivalds [1] constructs a quantum finite automaton (QFA) with O(log p) states recognizing the language Lp = {ai| i is divisible by p} with probability 1 - Ɛ , for any Ɛ > 0 and arbitrary prime p. In [4] we gave examples showing that the algorithm is applicable also to quantum automata of very limited size. However, the Ambainis-Freivalds algoritm is tailored to constructing a measure-many QFA (defined by Kondacs andWatrous [2]), which cannot be implemented on existing quantum computers. In this paper we modify the algorithm to construct a measure-once QFA of Moore and Crutchfield [3] and give examples of parameters for this automaton. We show for the lang…
Quantum Query Complexity for Some Graph Problems
2004
The paper [4] by H. Buhrman and R. de Wolf contains an impressive survey of solved and open problems in quantum query complexity, including many graph problems. We use recent results by A.Ambainis [1] to prove higher lower bounds for some of these problems. Some of our new lower bounds do not close the gap between the best upper and lower bounds. We prove in these cases that it is impossible to provide a better application of Ambainis’ technique for these problems.