On the state complexity of semi-quantum finite automata
arXiv:1307.2499 · doi:10.1051/ita/2014003
Abstract
Some of the most interesting and important results concerning quantum finite automata are those showing that they can recognize certain languages with (much) less resources than corresponding classical finite automata \cite{Amb98,Amb09,AmYa11,Ber05,Fre09,Mer00,Mer01,Mer02,Yak10,ZhgQiu112,Zhg12}. This paper shows three results of such a type that are stronger in some sense than other ones because (a) they deal with models of quantum automata with very little quantumness (so-called semi-quantum one- and two-way automata with one qubit memory only); (b) differences, even comparing with probabilistic classical automata, are bigger than expected; (c) a trade-off between the number of classical and quantum basis states needed is demonstrated in one case and (d) languages (or the promise problem) used to show main results are very simple and often explored ones in automata theory or in communication complexity, with seemingly little structure that could be utilized.
19 pages. We improve (make stronger) the results in section 3
References in corpus (6)
- Non-locality and Communication Complexity
- Unbounded-error quantum computation with small space bounds
- Superiority of exact quantum automata for promise problems
- Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
- Communication complexity of promise problems and their applications to finite automata
- Some Languages Recognized by Two-Way Finite Automata with Quantum and Classical States
Cited by in corpus (8)
- Generalizations of the distributed Deutsch-Jozsa promise problem
- On hybrid models of quantum finite automata
- Potential of quantum finite automata with exact acceptance
- Quantum finite automata: survey, status and research directions
- Communication complexity of promise problems and their applications to finite automata
- Exact quantum algorithms have advantage for almost all Boolean functions
- A Quantum Finite Automata Approach to Modeling the Chemical Reactions
- Time-space tradeoffs for two-way finite automata