Quantum pushdown automata with garbage tape

DOI10.1142/S0129054118500132MaRDI QIDQ4640342zbMATH OpenOpenAlexWikidataFDO

Authors Masaki Nakanishi

Publication date 17 May 2018

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.3449

zbMATH Keywords

deterministic pushdown automataquantum computation modelsquantum pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum computation (81P68)

Abstract: Several kinds of quantum pushdown automaton models have been proposed, and their computational power is investigated intensively. However, for some quantum pushdown automaton models, it is not known whether quantum models are at least as powerful as classical counterparts or not. This is due to the reversibility restriction. In this paper, we introduce a new quantum pushdown automaton model that has a garbage tape. This model can overcome the reversibility restriction by exploiting the garbage tape to store popped symbols. We show that the proposed model can simulate any quantum pushdown automaton with a classical stack as well as any probabilistic pushdown automaton. We also show that our model can solve a certain promise problem exactly while deterministic pushdown automata cannot. These results imply that our model is strictly more powerful than classical counterparts in the setting of exact, one-sided error and non-deterministic computation.

Recommendations

• Quantum pushdown automata with a garbage tape
• Computing and Combinatorics
• Quantum pushdown automata
• scientific article; zbMATH DE number 2079870
• scientific article; zbMATH DE number 2090014

Cites work

• scientific article; zbMATH DE number 3635490 (Why is no real title available?)
• scientific article; zbMATH DE number 2079870 (Why is no real title available?)
• scientific article; zbMATH DE number 2080917 (Why is no real title available?)
• scientific article; zbMATH DE number 1490010 (Why is no real title available?)
• scientific article; zbMATH DE number 1839459 (Why is no real title available?)
• A helpful result for proving inherent ambiguity
• Characterizations of 1-Way Quantum Finite Automata
• Efficient probability amplification in two-way quantum finite automata
• One-way probabilistic reversible and quantum one-counter automata.
• Quantum algorithms revisited
• Quantum automata and quantum grammars
• Quantum counter automata
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Quantum versus deterministic counter automata
• Rapid solution of problems by quantum computation
• Succinctness of two-way probabilistic and quantum finite automata
• Superiority of exact quantum automata for promise problems
• Superiority of one-way and realtime quantum machines
• Two-way finite automata with quantum and classical states.
• Unbounded-error quantum computation with small space bounds
• Various Aspects of Finite Quantum Automata
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs

Cited in

(5)

• Characterization of tree automata based on quantum logic
• Quantum pushdown automata with a garbage tape
• Pumping lemma for quantum automata
• Computing and Combinatorics
• On entropy and reversibility of pushdown dynamical systems

This page was built for publication: Quantum pushdown automata with garbage tape

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4640342)