Characterizations of one-way general quantum finite automata
From MaRDI portal
(Redirected from Publication:764358)
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.
Recommendations
Cites work
- A note on quantum sequential machines
- A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
- Algebraic results on quantum automata
- Characterization of sequential quantum machines
- Characterizations of 1-Way Quantum Finite Automata
- Characterizations of quantum automata
- Dense quantum coding and quantum finite automata
- Determination of equivalence between quantum sequential machines
- Determining the equivalence for one-way quantum finite automata
- Hierarchy and equivalence of multi-letter quantum finite automata
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 176733 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 2040892 (Why is no real title available?)
- scientific article; zbMATH DE number 1775384 (Why is no real title available?)
- scientific article; zbMATH DE number 1839459 (Why is no real title available?)
- scientific article; zbMATH DE number 2090013 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- scientific article; zbMATH DE number 3371972 (Why is no real title available?)
- Languages Recognized with Unbounded Error by Quantum Finite Automata
- Logical Reversibility of Computation
- Multi-letter quantum finite automata: decidability of the equivalence and minimization of states
- On the Size of One-way Quantum Finite Automata with Periodic Behaviors
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Probabilistic automata
- Quantum automata and quantum grammars
- Quantum automata for some multiperiodic languages
- Quantum finite automata with control language
- Regular languages accepted by quantum automata
- Small size quantum automata recognizing some regular languages
- Topological automata
- Two-way finite automata with quantum and classical states.
- Unbounded-error quantum computation with small space bounds
- Undecidability on quantum finite automata
Cited in
(35)- Some algebraic properties of measure-once two-way quantum finite automata
- Characterizations of quantum automata
- Improved constructions for succinct affine automata
- Affine automata verifiers
- Energy complexity of regular language recognition
- Equivalence checking of quantum finite-state machines
- Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
- On hybrid models of quantum finite automata
- Corrigendum to: ``Another approach to the equivalence of measure-many one-way quantum finite automata and its application
- Determining the equivalence for one-way quantum finite automata
- Lower bounds on the size of semi-quantum finite automata
- scientific article; zbMATH DE number 1688355 (Why is no real title available?)
- Language Recognition Power and Succinctness of Affine Automata
- Analysis of finite 1-qubit quantum automata unitary operators of which are rotations
- Quantum finite automata: a modern introduction
- Potential of quantum finite automata with exact acceptance
- Characterizations of 1-Way Quantum Finite Automata
- One-way finite automata with quantum and classical states
- State succinctness of two-way finite automata with quantum and classical states
- Another approach to the equivalence of measure-many one-way quantum finite automata and its application
- scientific article; zbMATH DE number 2044497 (Why is no real title available?)
- Exponentially more concise quantum recognition of non-RMM regular languages
- Quantum Markov chains: description of hybrid systems, decidability of equivalence, and model checking linear-time properties
- Promise problems solved by quantum and classical finite automata
- On the power of two-way multihead quantum finite automata
- scientific article; zbMATH DE number 7104930 (Why is no real title available?)
- On the computational power of affine automata
- Affine computation and affine automaton
- On the power of one-way automata with quantum and classical states
- Language recognition power and succinctness of affine automata
- Learning quantum finite automata with queries
- Energy complexity of regular languages
- Classical and quantum Merlin-Arthur automata
- On the complexity of minimizing probabilistic and quantum automata
- Latvian quantum finite state automata for unary languages
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)
