Superiority of one-way and realtime quantum machines

In automata theory, the quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to the QFAs augmented with counters or stacks. Moreover, to our knowledge, there is no result related to QFAs having more than one input head. In this paper, we focus on such generalizations of QFAs whose input head(s) operate(s) in one-way or realtime mode and present many superiority of them to their classical counterparts. Furthermore, we propose some open problems and conjectures in order to investigate the power of quantumness better. We also give some new results on classical computation.

• Publication year

  2011

• Venue

  RAIRO - Theoretical Informatics and Applications

• Publication date

  2011-02-15

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1051/ita/2012018arXiv 1102.3093
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Probabilistic ω-automata

  2012cited by this paper
• Quantum Computation and Quantum Information

  2012cited by this paper
• Proving the Power of Postselection

  2011cited by this paper
• Computation with Narrow CTCs

  2011cited by this paper
• Classical and quantum computation with small space bounds (PhD thesis)

  2011cited by this paper
• Quantum Counter Automata

  2011cited by this paper
• Superiority of exact quantum automata for promise problems

  2011cited by this paper
• Two-Tape Finite Automata with Quantum and Classical States

  2011cited by this paper
• Probabilistic and quantum finite automata with postselection

  2011cited by this paper
• Quantum computation with write-only memory

  2010cited by this paper
• Quantum function computation using sublogarithmic space (abstract & poster)

  2010cited by this paper
• Quantum function computation using sublogarithmic space (abstract&poster)

  2010cited by this paper
• A new family of nonstochastic languages

  2010cited by this paper
• Unbounded-error quantum computation with small space bounds

  2010influential reference
• Quantum Automata with Open Time Evolution

  2010cited by this paper
• Succinctness of two-way probabilistic and quantum finite automata

  2009cited by this paper
• Efficient probability amplification in two-way quantum finite automata

  2009cited by this paper
• Languages recognized by nondeterministic quantum finite automata

  2009influential reference
• Quantum Computational Complexity

  2008cited by this paper
• Languages Recognized with Unbounded Error by Quantum Finite Automata

  2008cited by this paper
• Various Aspects of Finite Quantum Automata

  2008cited by this paper
• Quantum automata for some multiperiodic languages

  2007cited by this paper
• Expressive Power of Quantum Pushdown Automata with Classical Stack Operations under the Perfect-Soundness Condition

  2006cited by this paper
• Quantum versus Classical Pushdown Automata in Exact Computation

  2005cited by this paper
• Small size quantum automata recognizing some regular languages

  2005cited by this paper
• Probabilistic automata

  2003cited by this paper
• Quantum versus deterministic counter automata

  2002cited by this paper
• On the Size of One-way Quantum Finite Automata with Periodic Behaviors

  2002cited by this paper
• An Introduction to Probabilistic Automata

  2002cited by this paper
• On the Power of Non-deterministic Quantum Finite Automata

  2002cited by this paper
• Dense quantum coding and quantum finite automata

  2002cited by this paper
• Analogies and di"erences between quantum and stochastic automata

  2001cited by this paper
• On the power of quantum pushdown automata with a classical stack and 1.5-way quantum finite automata

  2001cited by this paper
• Quantum versus Probabilistic One-Way Finite Automata with Counter

  2001cited by this paper
• One-way probabilistic reversible and quantum one-counter automata

  2000cited by this paper
• Quantum Pushdown Automata

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

  1999cited by this paper
• Space-Bounded Quantum Complexity

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

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

  1998cited by this paper
• Quantum automata and quantum grammars

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

  1997cited by this paper
• Quantum complexity theory

  1993cited by this paper
• Multihead One-Way Finite Automata

  1991cited by this paper
• Introduction to the theory of computation

  1989cited by this paper
• k+1 heads are better than k for PDA's

  1986cited by this paper
• Fast Probabilistic Algorithms

  1979cited by this paper
• Remarks on Blind and Partially Blind One-Way Multicounter Machines

  1978influential reference
• Generalized automata and stochastic languages

  1969cited by this paper
• Counter machines and counter languages

  1968cited by this paper
• On multi-head finite automata

  1965cited by this paper

• Quantum ω-Automata over Infinite Words and Their Relationships

  2019cites this paper
• New Results on Vector and Homing Vector Automata

  2019cites this paper
• Quantum finite automata: survey, status and research directions

  2019influential citation
• Quantum Pushdown Automata with Garbage Tape

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

  2018cites this paper
• Exact Affine Counter Automata

  2017cites this paper
• Affine counter automata

  2017cites this paper
• Affine Computation and Affine Automaton

  2016cites this paper
• Uncountable classical and quantum complexity classes

  2016cites this paper
• Automata and Quantum Computing

  2015influential citation
• oleh perkembangan teori otomata. Teori otomata merupakan disiplin ilmu yang mempelajari hal-hal yang berhubungan dengan perangkat komputer yang bersifat abstrak yang sering disebut dengan mesin (“machines”) [12]. Pada tahun 1930an, Alan Turing telah mengkaji mesin abstraksi yang telah memiliki kemam

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

  2014cites this paper
• Implications of Quantum Automata for Contextuality

  2014cites this paper
• New Results on the Minimum Amount of Useful Space

  2014cites this paper
• The Minimum Amount of Useful Space: New Results and New Directions

  2014cites this paper
• New results on classical and quantum counter automata

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

  2014cites this paper
• Classical and Quantum Counter Automata on Promise Problems

  2014cites this paper
• Real-Time Vector Automata

  2013cites this paper