6533b834fe1ef96bd129cb60
RESEARCH PRODUCT
Exact results for accepting probabilities of quantum automata
Arnolds KikustsAndris Ambainissubject
General Computer ScienceFOS: Physical sciences0102 computer and information sciences02 engineering and technologyUnitary transformationComputer Science::Computational Complexity01 natural sciencesTheoretical Computer ScienceCombinatoricsQuantum measurementFormal languageQuantum computation0202 electrical engineering electronic engineering information engineeringQuantum finite automataMathematicsQuantum computerQuantum PhysicsFinite-state machineMarkov chainExact resultsTransformation (function)010201 computation theory & mathematics020201 artificial intelligence & image processingQuantum Physics (quant-ph)Finite automataComputer Science::Formal Languages and Automata TheoryComputer Science(all)description
One of the properties of Kondacs-Watrous model of quantum finite automata (QFA) is that the probability of the correct answer for a QFA cannot be amplified arbitrarily. In this paper, we determine the maximum probabilities achieved by QFAs for several languages. In particular, we show that any language that is not recognized by an RFA (reversible finite automaton) can be recognized by a QFA with probability at most 0.7726...
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2001-09-26 | Theoretical Computer Science |