6533b7d8fe1ef96bd126ae70
RESEARCH PRODUCT
Quantum counter automata
Abuzer YakaryilmazA. C. Cem Saysubject
SoundnessFOS: Computer and information sciencesQuantum PhysicsGeneralizationComputer scienceProbabilistic logicFOS: Physical sciences0102 computer and information sciences02 engineering and technologyComputational Complexity (cs.CC)01 natural sciencesAutomatonAlgebraComputer Science - Computational Complexity010201 computation theory & mathematics0202 electrical engineering electronic engineering information engineeringComputer Science (miscellaneous)Quantum finite automata020201 artificial intelligence & image processingPoint (geometry)Quantum Physics (quant-ph)Quantumdescription
The question of whether quantum real-time one-counter automata (rtQ1CAs) can outperform their probabilistic counterparts has been open for more than a decade. We provide an affirmative answer to this question, by demonstrating a non-context-free language that can be recognized with perfect soundness by a rtQ1CA. This is the first demonstration of the superiority of a quantum model to the corresponding classical one in the real-time case with an error bound less than 1. We also introduce a generalization of the rtQ1CA, the quantum one-way one-counter automaton (1Q1CA), and show that they too are superior to the corresponding family of probabilistic machines. For this purpose, we provide general definitions of these models that reflect the modern approach to the definition of quantum finite automata, and point out some problems with previous results. We identify several remaining open problems.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2011-05-01 |