For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On the Power of Non-deterministic Quantum Finite Automata
Masaki NAKANISHI Takao INDOH Kiyoharu HAMAGUCHI Toshinobu KASHIWABARA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2002/02/01
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
quantum computation, quantum finite automaton, non-deterministic finite automaton, regular language,
Full Text: PDF(470.6KB)>>
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.