We compare the descriptional power of quantum finite automata with control language (qfcs) and deterministic finite automata (dfas). By suitably adapting Rabin’s technique, we show how to convert any given qfc to an equivalent dfa, incurring in an at most exponential size increase. This enables us to state a lower bound on the size of qfcs, which is logarithmic in the size of equivalent minimal dfas. In turn, this result yields analogous size lower bounds for several models of quantum finite automata in the literature.
Size lower bounds for quantum automata / M.P. Bianchi, C. Mereghetti, B. Palano (LECTURE NOTES IN COMPUTER SCIENCE). - In: Unconventional Computation and Natural Computation / [a cura di] G. Mauri, A. Dennunzio, L. Manzoni, A.E. Porreca. - Berlin : Springer, 2013. - ISBN 9783642390739. - pp. 19-30 (( Intervento presentato al 12. convegno International Conference on Unconventional Computation and Natural Computation (UCNC) tenutosi a Milano nel 2013 [10.1007/978-3-642-39074-6_4].
Size lower bounds for quantum automata
M.P. BianchiPrimo
;C. MereghettiSecondo
;B. PalanoUltimo
2013
Abstract
We compare the descriptional power of quantum finite automata with control language (qfcs) and deterministic finite automata (dfas). By suitably adapting Rabin’s technique, we show how to convert any given qfc to an equivalent dfa, incurring in an at most exponential size increase. This enables us to state a lower bound on the size of qfcs, which is logarithmic in the size of equivalent minimal dfas. In turn, this result yields analogous size lower bounds for several models of quantum finite automata in the literature.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
272.11 kB
Formato
Adobe PDF
|
272.11 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.