Characterizations of one-way general quantum finite automata
From MaRDI portal
Publication:764358
DOI10.1016/J.TCS.2011.10.021zbMATH Open1235.68102DBLPjournals/tcs/LiQZLWM12arXiv0911.3266OpenAlexW2008943448WikidataQ59196660 ScholiaQ59196660MaRDI QIDQ764358FDOQ764358
Authors: Lvzhou Li, Xiang Fu Zou, Lihua Wu, Paulo Mateus, Daowen Qiu, Lv-Jun Li 
Publication date: 13 March 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: In this paper we study a generalized model named one-way general quantum finite automata} (1gQFA), in which each symbol in the input alphabet induces a trace-preserving quantum operation, instead of a unitary transformation. Two different kinds of 1gQFA will be studied: measure-once one-way general quantum finite automata} (MO-1gQFA), and measure-many one-way general quantum finite automata (MM-1gQFA). We prove that MO-1gQFA recognize, with bounded error, precisely the set of all regular languages. We prove that MM-1gQFA also recognize only regular languages with bounded error. Thus, MM-1gQFA and MO-1gQFA have the same language recognition power, which is greatly different from the conventional case in which the number of times the measurement is performed in the computation generally affects the language recognition power of one-way QFA. Finally, we present a sufficient and necessary condition for two MM-1gQFA to be equivalent.
Full work available at URL: https://arxiv.org/abs/0911.3266
Recommendations
Formal languages and automata (68Q45) Quantum algorithms and complexity in the theory of computing (68Q12)
Cites Work
- Two-way finite automata with quantum and classical states.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Unbounded-error quantum computation with small space bounds
- Probabilistic automata
- Title not available (Why is that?)
- Quantum finite automata with control language
- Title not available (Why is that?)
- Logical Reversibility of Computation
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
- Quantum automata and quantum grammars
- Hierarchy and equivalence of multi-letter quantum finite automata
- Algebraic results on quantum automata
- Determination of equivalence between quantum sequential machines
- Determining the equivalence for one-way quantum finite automata
- Characterizations of 1-Way Quantum Finite Automata
- Dense quantum coding and quantum finite automata
- Quantum automata for some multiperiodic languages
- Small size quantum automata recognizing some regular languages
- Title not available (Why is that?)
- Title not available (Why is that?)
- Characterizations of quantum automata
- A note on quantum sequential machines
- Undecidability on quantum finite automata
- Languages Recognized with Unbounded Error by Quantum Finite Automata
- Regular languages accepted by quantum automata
- Topological automata
- On the Size of One-way Quantum Finite Automata with Periodic Behaviors
- Multi-letter quantum finite automata: decidability of the equivalence and minimization of states
- Characterization of sequential quantum machines
- Title not available (Why is that?)
Cited In (34)
- State succinctness of two-way finite automata with quantum and classical states
- On the power of one-way automata with quantum and classical states
- On the computational power of affine automata
- Title not available (Why is that?)
- Quantum Markov chains: description of hybrid systems, decidability of equivalence, and model checking linear-time properties
- Lower bounds on the size of semi-quantum finite automata
- Analysis of finite 1-qubit quantum automata unitary operators of which are rotations
- Exponentially more concise quantum recognition of non-RMM regular languages
- Equivalence checking of quantum finite-state machines
- Promise problems solved by quantum and classical finite automata
- Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
- Affine computation and affine automaton
- Title not available (Why is that?)
- Corrigendum to: ``Another approach to the equivalence of measure-many one-way quantum finite automata and its application
- Another approach to the equivalence of measure-many one-way quantum finite automata and its application
- Some algebraic properties of measure-once two-way quantum finite automata
- One-way finite automata with quantum and classical states
- Potential of quantum finite automata with exact acceptance
- Determining the equivalence for one-way quantum finite automata
- On hybrid models of quantum finite automata
- Characterizations of quantum automata
- Language recognition power and succinctness of affine automata
- Energy complexity of regular languages
- One-way reversible and quantum finite automata with advice
- Energy complexity of regular language recognition
- Characterizations of 1-Way Quantum Finite Automata
- On the power of two-way multihead quantum finite automata
- On the complexity of minimizing probabilistic and quantum automata
- Quantum finite automata: a modern introduction
- Classical and Quantum Counter Automata on Promise Problems
- Title not available (Why is that?)
- Improved constructions for succinct affine automata
- Affine automata verifiers
- Language Recognition Power and Succinctness of Affine Automata
This page was built for publication: Characterizations of one-way general quantum finite automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764358)
