On the Power of Non-deterministic Quantum Finite Automata

Masaki NAKANISHI  Takao INDOH  Kiyoharu HAMAGUCHI  Toshinobu KASHIWABARA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E85-D   No.2   pp.327-332
Publication Date: 2002/02/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
Category: 
Keyword: 
quantum computation,  quantum finite automaton,  non-deterministic finite automaton,  regular language,  

Full Text: PDF(470.6KB)>>
Buy this Article




Summary: 
The class NQP was proposed as the class of problems that are solvable by non-deterministic quantum Turing machines in polynomial time. In this paper, we introduce non-deterministic quantum finite automata in which the same non-determinism as in non-deterministic quantum Turing machines is applied. We compare non-deterministic quantum finite automata with the classical counterparts, and show that (unlike the case of classical finite automata) the class of languages recognizable by non-deterministic quantum finite automata properly contains the class of all regular languages.