Characterizations of one-way general quantum finite automata
From MaRDI portal
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
- 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?)
- A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
- A note on quantum sequential machines
- 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
- 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
(33)- Improved constructions for succinct affine automata
- Some algebraic properties of measure-once two-way quantum finite automata
- Promise problems solved by quantum and classical finite automata
- Learning quantum finite automata with queries
- Corrigendum to: ``Another approach to the equivalence of measure-many one-way quantum finite automata and its application
- Characterizations of 1-Way Quantum Finite Automata
- Language recognition power and succinctness of affine automata
- Another approach to the equivalence of measure-many one-way quantum finite automata and its application
- One-way finite automata with quantum and classical states
- State succinctness of two-way finite automata with quantum and classical states
- Affine computation and affine automaton
- Analysis of finite 1-qubit quantum automata unitary operators of which are rotations
- scientific article; zbMATH DE number 2044497 (Why is no real title available?)
- scientific article; zbMATH DE number 1688355 (Why is no real title available?)
- Quantum finite automata: a modern introduction
- On the power of one-way automata with quantum and classical states
- On the computational power of affine automata
- Determining the equivalence for one-way quantum finite automata
- On the complexity of minimizing probabilistic and quantum automata
- Exponentially more concise quantum recognition of non-RMM regular languages
- Affine automata verifiers
- Equivalence checking of quantum finite-state machines
- On hybrid models of quantum finite automata
- On the power of two-way multihead quantum finite automata
- Energy complexity of regular languages
- Potential of quantum finite automata with exact acceptance
- Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
- scientific article; zbMATH DE number 7104930 (Why is no real title available?)
- Language Recognition Power and Succinctness of Affine Automata
- Lower bounds on the size of semi-quantum finite automata
- Characterizations of quantum automata
- Energy complexity of regular language recognition
- Quantum Markov chains: description of hybrid systems, decidability of equivalence, and model checking linear-time properties
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)
