Characterizations of one-way general quantum finite automata

DOI10.1016/j.tcs.2011.10.021zbMath1235.68102arXiv0911.3266OpenAlexW2008943448WikidataQ59196660 ScholiaQ59196660MaRDI QIDQ764358

Lihua Wu, Xiangfu Zou, Paulo Mateus, Lvzhou Li, Dao Wen Qiu, Lv-Jun Li

Publication date: 13 March 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0911.3266

zbMATH Keywords

equivalenceformal languagesregular languagesquantum finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (24)

Lower bounds on the size of semi-quantum finite automata ⋮ One-Way Finite Automata with Quantum and Classical States ⋮ Affine automata verifiers ⋮ Energy complexity of regular language recognition ⋮ Unnamed Item ⋮ Quantum Finite Automata: A Modern Introduction ⋮ State succinctness of two-way finite automata with quantum and classical states ⋮ Classical and Quantum Counter Automata on Promise Problems ⋮ Potential of Quantum Finite Automata with Exact Acceptance ⋮ Language recognition power and succinctness of affine automata ⋮ On the Power of One-Way Automata with Quantum and Classical States ⋮ Energy complexity of regular languages ⋮ Equivalence checking of quantum finite-state machines ⋮ 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 complexity of minimizing probabilistic and quantum automata ⋮ On the Computational Power of Affine Automata ⋮ Affine Computation and Affine Automaton ⋮ Language Recognition Power and Succinctness of Affine Automata ⋮ On the power of two-way multihead quantum finite automata ⋮ Improved constructions for succinct affine automata ⋮ Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata ⋮ On hybrid models of quantum finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unbounded-error quantum computation with small space bounds
• Multi-letter quantum finite automata: decidability of the equivalence and minimization of states
• A note on quantum sequential machines
• Quantum automata and quantum grammars
• Characterization of sequential quantum machines
• Two-way finite automata with quantum and classical states.
• Regular languages accepted by quantum automata
• Characterizations of quantum automata
• Hierarchy and equivalence of multi-letter quantum finite automata
• Algebraic results on quantum automata
• Quantum automata for some multiperiodic languages
• Small size quantum automata recognizing some regular languages
• Determination of equivalence between quantum sequential machines
• Determining the equivalence for one-way quantum finite automata
• Topological automata
• Undecidability on quantum finite automata
• Characterizations of 1-Way Quantum Finite Automata
• Languages Recognized with Unbounded Error by Quantum Finite Automata
• Quantum finite automata with control language
• Dense quantum coding and quantum finite automata
• A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• On the Size of One-way Quantum Finite Automata with Periodic Behaviors
• Probabilistic automata
• Logical Reversibility of Computation

This page was built for publication: Characterizations of one-way general quantum finite automata