The Complexity of Probabilistic versus Quantum Finite Automata

Simple item page
dc.creatorMidrijanis, Gatis
dc.date2003-09-09
dc.date.accessioned2026-07-07T06:07:48Z
dc.date.available2026-07-07T06:07:48Z
dc.descriptionWe present a language $L_n$ which is recognizable by a probabilistic finite automaton (PFA) with probability $1 - ε$ for all $ε> 0$ with $O(log^2n)$ states, with a deterministic finite automaton (DFA) with O(n) states, but a quantum finite automaton (QFA) needs at least $2^{Ω(n/ \log n)}$ states.
dc.description6 pages, 2 figures
dc.identifierhttps://arxiv.org/abs/quant-ph/0309080
dc.identifierhttp://arxiv.org/abs/quant-ph/0309080
dc.identifierSOFSEM 2002 Proceedings,, pp. 273-278
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/91419
dc.subjectQuantum Physics
dc.titleThe Complexity of Probabilistic versus Quantum Finite Automata
dc.typetext

Files

Collections

arXiv