Quantum pushdown automata with garbage tape

DOI10.1142/S0129054118500132zbMATH Open1390.68411arXiv1402.3449OpenAlexW3035685209WikidataQ129870259 ScholiaQ129870259MaRDI QIDQ4640342FDOQ4640342

Masaki Nakanishi

Publication date: 17 May 2018

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

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.

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

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

zbMATH Keywords

deterministic pushdown automataquantum computation modelsquantum pushdown automata

Mathematics Subject Classification ID

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

Cites Work

• Two-way finite automata with quantum and classical states.
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Title not available (Why is that?)
• Unbounded-error quantum computation with small space bounds
• Quantum algorithms revisited
• Rapid solution of problems by quantum computation
• Quantum automata and quantum grammars
• Characterizations of 1-Way Quantum Finite Automata
• Superiority of exact quantum automata for promise problems
• Quantum computation with write-only memory
• Classical and Quantum Counter Automata on Promise Problems
• Various Aspects of Finite Quantum Automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• One-way probabilistic reversible and quantum one-counter automata.
• Title not available (Why is that?)
• Title not available (Why is that?)
• One-way reversible and quantum finite automata with advice
• Efficient probability amplification in two-way quantum finite automata
• Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs
• A helpful result for proving inherent ambiguity
• Title not available (Why is that?)
• QUANTUM COUNTER AUTOMATA
• Superiority of one-way and realtime quantum machines
• Quantum versus deterministic counter automata

Cited In (4)

• Characterization of tree automata based on quantum logic
• 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)