IEICE TRANSACTIONS on Information
On the Power of Non-deterministic Quantum Finite Automata
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E85-D No.2 pp.327-332
- Publication Date
- 2002/02/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Masaki NAKANISHI, Takao INDOH, Kiyoharu HAMAGUCHI, Toshinobu KASHIWABARA, "On the Power of Non-deterministic Quantum Finite Automata" in IEICE TRANSACTIONS on Information,
vol. E85-D, no. 2, pp. 327-332, February 2002, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e85-d_2_327/_p
Copy
@ARTICLE{e85-d_2_327,
author={Masaki NAKANISHI, Takao INDOH, Kiyoharu HAMAGUCHI, Toshinobu KASHIWABARA, },
journal={IEICE TRANSACTIONS on Information},
title={On the Power of Non-deterministic Quantum Finite Automata},
year={2002},
volume={E85-D},
number={2},
pages={327-332},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={February},}
Copy
TY - JOUR
TI - On the Power of Non-deterministic Quantum Finite Automata
T2 - IEICE TRANSACTIONS on Information
SP - 327
EP - 332
AU - Masaki NAKANISHI
AU - Takao INDOH
AU - Kiyoharu HAMAGUCHI
AU - Toshinobu KASHIWABARA
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E85-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2002
AB - 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.
ER -
English
