6533b852fe1ef96bd12ab85a
RESEARCH PRODUCT
Superiority of exact quantum automata for promise problems
Abuzer YakaryilmazAndris Ambainissubject
FOS: Computer and information sciencesFormal Languages and Automata Theory (cs.FL)Timed automatonFOS: Physical sciencesComputer Science - Formal Languages and Automata Theory0102 computer and information sciencesω-automatonComputational Complexity (cs.CC)01 natural sciencesTheoretical Computer ScienceDeterministic automatonApplied mathematicsQuantum finite automataTwo-way deterministic finite automatonNondeterministic finite automaton0101 mathematicsMathematicsDiscrete mathematicsQuantum Physics010102 general mathematicsComputer Science ApplicationsComputer Science - Computational Complexity010201 computation theory & mathematicsSignal ProcessingAutomata theoryQuantum Physics (quant-ph)Computer Science::Formal Languages and Automata TheoryInformation SystemsQuantum cellular automatondescription
In this note, we present an infinite family of promise problems which can be solved exactly by just tuning transition amplitudes of a two-state quantum finite automata operating in realtime mode, whereas the size of the corresponding classical automata grow without bound.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2011-01-20 |