Paper Info
Title
Exact quantum algorithms for promise problems in automata theory
Abstract
In this note, we show that quantum finite automata can be polynomially more succinct than their classical counterparts for promise problems in case of exact computation. Additionally, in terms of language recognition, the same result is shown to be valid up to a constant factor depending on how bigger the size of the alphabet is.
Year
Venue
Keywords
2011
Clinical Orthopaedics and Related Research
finite automata,quantum algorithm,automata theory
Field
DocType
Volume
Quantum finite automata,Discrete mathematics,Automata theory,Nondeterministic finite automaton,Deterministic finite automaton,Quantum algorithm,Quantum cellular automaton,Mathematics,Theory of computation,ω-automaton
Journal
abs/1101.3
Citations 
PageRank 
References 
0
0.34
9
Authors
1
Name
Order
Citations
PageRank
Abuzer Yakaryilmaz116825.31