Expressive Power of Quantum Pushdown Automata with Classical Stack Operations under the Perfect-Soundness Condition

Masaki NAKANISHI; Kiyoharu HAMAGUCHI; Toshinobu KASHIWABARA

doi:10.1093/ietisy/e89-d.3.1120

Expressive Power of Quantum Pushdown Automata with Classical Stack Operations under the Perfect-Soundness Condition

Masaki NAKANISHI, Kiyoharu HAMAGUCHI, Toshinobu KASHIWABARA

Full Text Views

0

Share
Cite this

Summary :

One important question for quantum computing is whether a computational gap exists between models that are allowed to use quantum effects and models that are not. Several types of quantum computation models have been proposed, including quantum finite automata and quantum pushdown automata (with a quantum pushdown stack). It has been shown that some quantum computation models are more powerful than their classical counterparts and others are not since quantum computation models are required to obey such restrictions as reversible state transitions. In this paper, we investigate the power of quantum pushdown automata whose stacks are assumed to be implemented as classical devices, and show that they are strictly more powerful than their classical counterparts under the perfect-soundness condition, where perfect-soundness means that an automaton never accepts a word that is not in the language. That is, we show that our model can simulate any probabilistic pushdown automata and also show that there is a non-context-free language which quantum pushdown automata with classical stack operations can recognize with perfect soundness.

Publication: IEICE TRANSACTIONS on Information Vol.E89-D No.3 pp.1120-1127

Publication Date: 2006/03/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e89-d.3.1120

Type of Manuscript: PAPER

Category: Computation and Computational Models

Cite this

Copy

Masaki NAKANISHI, Kiyoharu HAMAGUCHI, Toshinobu KASHIWABARA, "Expressive Power of Quantum Pushdown Automata with Classical Stack Operations under the Perfect-Soundness Condition" in IEICE TRANSACTIONS on Information, vol. E89-D, no. 3, pp. 1120-1127, March 2006, doi: 10.1093/ietisy/e89-d.3.1120.
Abstract: One important question for quantum computing is whether a computational gap exists between models that are allowed to use quantum effects and models that are not. Several types of quantum computation models have been proposed, including quantum finite automata and quantum pushdown automata (with a quantum pushdown stack). It has been shown that some quantum computation models are more powerful than their classical counterparts and others are not since quantum computation models are required to obey such restrictions as reversible state transitions. In this paper, we investigate the power of quantum pushdown automata whose stacks are assumed to be implemented as classical devices, and show that they are strictly more powerful than their classical counterparts under the perfect-soundness condition, where perfect-soundness means that an automaton never accepts a word that is not in the language. That is, we show that our model can simulate any probabilistic pushdown automata and also show that there is a non-context-free language which quantum pushdown automata with classical stack operations can recognize with perfect soundness.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e89-d.3.1120/_p

Copy

@ARTICLE{e89-d_3_1120,
author={Masaki NAKANISHI, Kiyoharu HAMAGUCHI, Toshinobu KASHIWABARA, },
journal={IEICE TRANSACTIONS on Information},
title={Expressive Power of Quantum Pushdown Automata with Classical Stack Operations under the Perfect-Soundness Condition},
year={2006},
volume={E89-D},
number={3},
pages={1120-1127},
abstract={One important question for quantum computing is whether a computational gap exists between models that are allowed to use quantum effects and models that are not. Several types of quantum computation models have been proposed, including quantum finite automata and quantum pushdown automata (with a quantum pushdown stack). It has been shown that some quantum computation models are more powerful than their classical counterparts and others are not since quantum computation models are required to obey such restrictions as reversible state transitions. In this paper, we investigate the power of quantum pushdown automata whose stacks are assumed to be implemented as classical devices, and show that they are strictly more powerful than their classical counterparts under the perfect-soundness condition, where perfect-soundness means that an automaton never accepts a word that is not in the language. That is, we show that our model can simulate any probabilistic pushdown automata and also show that there is a non-context-free language which quantum pushdown automata with classical stack operations can recognize with perfect soundness.},
keywords={},
doi={10.1093/ietisy/e89-d.3.1120},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Expressive Power of Quantum Pushdown Automata with Classical Stack Operations under the Perfect-Soundness Condition
T2 - IEICE TRANSACTIONS on Information
SP - 1120
EP - 1127
AU - Masaki NAKANISHI
AU - Kiyoharu HAMAGUCHI
AU - Toshinobu KASHIWABARA
PY - 2006
DO - 10.1093/ietisy/e89-d.3.1120
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E89-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2006
AB - One important question for quantum computing is whether a computational gap exists between models that are allowed to use quantum effects and models that are not. Several types of quantum computation models have been proposed, including quantum finite automata and quantum pushdown automata (with a quantum pushdown stack). It has been shown that some quantum computation models are more powerful than their classical counterparts and others are not since quantum computation models are required to obey such restrictions as reversible state transitions. In this paper, we investigate the power of quantum pushdown automata whose stacks are assumed to be implemented as classical devices, and show that they are strictly more powerful than their classical counterparts under the perfect-soundness condition, where perfect-soundness means that an automaton never accepts a word that is not in the language. That is, we show that our model can simulate any probabilistic pushdown automata and also show that there is a non-context-free language which quantum pushdown automata with classical stack operations can recognize with perfect soundness.
ER -