One-Way Finite Automata with Quantum and Classical States

DOI10.1007/978-3-642-31644-9_19zbMath1330.68183arXiv1112.2022OpenAlexW2240904545MaRDI QIDQ3166958

Jozef Gruska, Shenggen Zheng, Lvzhou Li, Dao Wen Qiu

Publication date: 1 November 2012

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Related Items (17)

Lower bounds on the size of semi-quantum finite automata ⋮ Time-Space Complexity Advantages for Quantum Computing ⋮ Complexity of Promise Problems on Classical and Quantum Automata ⋮ Quantum Finite Automata: A Modern Introduction ⋮ From Quantum Query Complexity to State Complexity ⋮ State succinctness of two-way finite automata with quantum and classical states ⋮ Size lower bounds for quantum automata ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Generalizations of the distributed Deutsch–Jozsa promise problem ⋮ 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 ⋮ Application of distributed semi-quantum computing model in phase estimation ⋮ Promise problems solved by quantum and classical finite automata ⋮ Quantum finite automata: advances on Bertoni's ideas ⋮ Uncountable classical and quantum complexity classes ⋮ On relation between linear temporal logic and quantum finite automata ⋮ On hybrid models of quantum finite automata

Cites Work

• State succinctness of two-way finite automata with quantum and classical states
• Two-tape finite automata with quantum and classical states
• Unbounded-error quantum computation with small space bounds
• Characterizations of one-way general quantum finite automata
• Improved constructions of quantum automata
• A note on quantum sequential machines
• Quantum automata and quantum grammars
• Two-way finite automata with quantum and classical states.
• Hierarchy and equivalence of multi-letter quantum finite automata
• Algebraic results on quantum automata
• Small size quantum automata recognizing some regular languages
• Determining the equivalence for one-way quantum finite automata
• Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
• Characterizations of 1-Way Quantum Finite Automata
• Quantum finite automata with control language
• Dense quantum coding and quantum finite automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: One-Way Finite Automata with Quantum and Classical States