Exact results for accepting probabilities of quantum automata

Autor:	Arnolds Kikusts, Andris Ambainis
Jazyk:	angličtina
Předmět:	General Computer Science FOS: Physical sciences 0102 computer and information sciences 02 engineering and technology Unitary transformation Computer Science::Computational Complexity 01 natural sciences Theoretical Computer Science Combinatorics Quantum measurement Formal language Quantum computation 0202 electrical engineering electronic engineering information engineering Quantum finite automata Mathematics Quantum computer Quantum Physics Finite-state machine Markov chain Exact results Transformation (function) 010201 computation theory & mathematics 020201 artificial intelligence & image processing Quantum Physics (quant-ph) Finite automata Computer Science::Formal Languages and Automata Theory Computer Science(all)
Zdroj:	MFCS
ISSN:	0304-3975
DOI:	10.1016/S0304-3975(02)00393-6
Popis:	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... Comment: 26 pages, 4 figures, submitted to Theoretical Computer Science (earlier version at STACS'01)
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0903cb42c3fd977270392694bb2d076b Zobrazit plný text záznamu