On the state complexity of semi-quantum finite automata

DOI10.1051/ita/2014003zbMath1292.81027OpenAlexW2744499508MaRDI QIDQ5166503

Shenggen Zheng, Jozef Gruska, Dao Wen Qiu

Publication date: 27 June 2014

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.744.5315

zbMATH Keywords

quantum computingstate complexityquantum finite automatasemi-quantum finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum computation (81P68) Descriptive complexity and finite models (68Q19) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (13)

Lower bounds on the size of semi-quantum finite automata ⋮ Time-Space Complexity Advantages for Quantum Computing ⋮ Potential of Quantum Finite Automata with Exact Acceptance ⋮ Generalizations of the distributed Deutsch–Jozsa promise problem ⋮ 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 ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice ⋮ On the power of two-way multihead quantum finite automata ⋮ On coverings of products of uninitialized sequential quantum machines ⋮ Quantum State Complexity of Formal Languages ⋮ On hybrid models of quantum finite automata

This page was built for publication: On the state complexity of semi-quantum finite automata