On the state complexity of semi-quantum finite automata

DOI10.1051/ITA/2014003MaRDI QIDQ5166503zbMATH OpenOpenAlexFDO

Authors Shenggen Zheng, Jozef Gruska, Daowen 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 computingquantum finite automatasemi-quantum finite automatastate complexity

Mathematics Subject Classification ID

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

Recommendations

• On the state complexity of semi-quantum finite automata
• Lower bounds on the size of semi-quantum finite automata
• On finite automata with quantum and classical states
• One-way finite automata with quantum and classical states
• From quantum query complexity to state complexity

Cited in

(15)

• Quantum Markov chains: description of hybrid systems, decidability of equivalence, and model checking linear-time properties
• On the state complexity of semi-quantum finite automata
• Lower bounds on the size of semi-quantum finite automata
• From quantum query complexity to state complexity
• Generalizations of the distributed Deutsch-Jozsa promise problem
• Promise problems solved by quantum and classical finite automata
• Quantum state complexity of formal languages
• Potential of quantum finite automata with exact acceptance
• On hybrid models of quantum finite automata
• On the power of two-way multihead quantum finite automata
• Superposition as memory: unlocking quantum automatic complexity
• Time-Space Complexity Advantages for Quantum Computing
• Application of distributed semi-quantum computing model in phase estimation
• Quantum finite automata: advances on Bertoni's ideas
• On coverings of products of uninitialized sequential quantum machines

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5166503)