Quantum Pushdown Automata

Quantum finite automata, as well as quantum pushdown automata were first introduced by C. Moore, J. P. Crutchfield [13]. In this paper we introduce the notion of quantum pushdown automata (QPA) in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of [11]. It is established that the unitarity criteria of QPA are not equivalent to the corresponding unitarity criteria of quantum Turing machines [4]. We show that QPA can recognize every regular language. Finally we present some simple languages recognized by QPA, two of them are not recognizable by deterministic pushdown automata and one seems to be not recognizable by probabilistic pushdown automata as well.

• Publication year

  2000

• Venue

  Conference on Current Trends in Theory and Practice of Informatics

• Publication date

  2000-11-25

• Fields of study

  Physics, Computer Science

• Identifiers
  DOI 10.1007/3-540-44411-4_22arXiv quant-ph/0102054
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The class of languages recognizable by 1-way quantum finite automata is not closed under union

  2000cited by this paper
• Probabilities to Accept Languages by Quantum Finite Automata

  1999cited by this paper
• Simulating physics with computers

  1999cited by this paper
• A Cat-State Benchmark on a Seven Bit Quantum Computer

  1999cited by this paper
• Characterizations of 1-Way Quantum Finite Automata

  1999cited by this paper
• Quantum Finite One-Counter Automata

  1999cited by this paper
• Quantum Challenges

  1999cited by this paper
• Quantum Finite Multitape Automata

  1999cited by this paper
• 1-way quantum finite automata: strengths, weaknesses and generalizations

  1998cited by this paper
• On the power of quantum finite state automata

  1997influential reference
• Quantum automata and quantum grammars

  1997influential reference
• Quantum error correction via codes over GF(4)

  1996cited by this paper
• A decision procedure for unitary linear quantum cellular automata

  1996cited by this paper
• Algorithms for quantum computation: discrete logarithms and factoring

  1994cited by this paper
• Quantum complexity theory

  1993cited by this paper
• Review: Eitan Gurari, An Introduction to the Theory of Computation

  1991influential reference
• Introduction to the theory of computation

  1989cited by this paper
• Quantum theory, the Church–Turing principle and the universal quantum computer

  1985cited by this paper

• On Quantum Context-Free Grammars

  2025cites this paper
• Notes on Stack Machines and Quantum Stack Machines

  2025cites this paper
• Push-down automata as sequential generators of highly entangled states

  2023cites this paper
• Characterization of Tree Automata Based on Quantum Logic

  2022cites this paper
• Decompositions of average probability uninitialized sequential quantum machines

  2022influential citation
• RNA-2QCFA: Evolving Two-way Quantum Finite Automata with Classical States for RNA Secondary Structures

  2020influential citation
• On Coverings of Products of Uninitialized Sequential Quantum Machines

  2019cites this paper
• Model-checking quantum systems

  2018cites this paper
• On the Power of Quantum Queue Automata in Real-time

  2018influential citation
• Analysis of quantum programs

  2016cites this paper
• Magic coins are useful for small-space quantum machines

  2014cites this paper
• Quantum Pushdown Automata with a Garbage Tape

  2014cites this paper
• Quantum Pushdown Automata with Classical Stack and Tape Head

  2014cites this paper
• Push down automata vs quantum push down automata

  2012cites this paper
• Language classes and quantum nite automata

  2012cites this paper
• Models of Pushdown Automata with Reset

  2011cites this paper
• Superiority of one-way and realtime quantum machines

  2011cites this paper
• On the Weakness of One-Way Quantum Pushdown Automata

  2010cites this paper
• An overview of quantum computation models: quantum automata

  2008influential citation
• Automata theory based on quantum logic: Reversibilities and pushdown automata

  2007cites this paper
• Determining the equivalence for one-way quantum finite automata

  2007cites this paper
• Determination of equivalence between quantum sequential machines

  2006cites this paper
• Expressive Power of Quantum Pushdown Automata with Classical Stack Operations under the Perfect-Soundness Condition

  2006cites this paper
• A Polynomial-Time Algorithm for the Equivalence between Quantum Sequential Machines

  2006cites this paper
• Automata with Quantum and Classical Resources

  2006cites this paper
• Simulations of Quantum Turing Machines by Quantum Multi-Stack Machines

  2005cites this paper
• QUANTUM PUSHDOWN AUTOMATA THAT CAN DETERMINISTICALLY SOLVE A CERTAIN PROBLEM

  2005cites this paper
• Ja n 20 05 Simulations of Quantum Turing Machines by Quantum Multi-Counter Machines

  2005cites this paper
• Quantum versus Classical Pushdown Automata in Exact Computation

  2005cites this paper
• Characterizations of quantum automata

  2004influential citation
• An application of quantum finite automata to interactive proof systems

  2004cites this paper
• On the Power of One-Sided Error Quantum Pushdown Automata with Classical Stack Operations

  2003cites this paper
• Grammar Theory Based on Quantum Logic

  2003cites this paper
• Computing with words via Turing machines: a formal approach

  2003cites this paper
• Quantum Pushdown Automata

  2002influential citation
• Quantum automata and quantum computing

  2002cites this paper
• Quantum versus deterministic counter automata

  2002cites this paper
• Two-way Quantum One-counter Automata

  2001cites this paper