Lower bounds on the size of semi-quantum finite automata
From MaRDI portal
Publication:264532
DOI10.1016/J.TCS.2015.09.031zbMATH Open1417.68086arXiv1502.02839OpenAlexW2193399559MaRDI QIDQ264532FDOQ264532
Authors: Lvzhou Li, Daowen Qiu 
Publication date: 31 March 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: In the literature, there exist several interesting hybrid models of finite automata which have both quantum and classical states. We call them semi-quantum automata. In this paper, we compare the descriptional power of these models with that of DFA. Specifically, we present a uniform method that gives a lower bound on the size of the three existing main models of semi-quantum automata, and this bound shows that semi-quantum automata can be at most exponentially more concise than DFA. Compared with a recent work (Bianchi, Mereghetti, Palano, Theoret. Comput. Sci., 551(2014), 102-115), our method shows the following two advantages: (i) our method is much more concise; and (ii) our method is universal, since it is applicable to the three existing main models of semi-quantum automata, instead of only a specific model.
Full work available at URL: https://arxiv.org/abs/1502.02839
Recommendations
Cites Work
- Two-way finite automata with quantum and classical states.
- Title not available (Why is that?)
- Title not available (Why is that?)
- On hybrid models of quantum finite automata
- One-way finite automata with quantum and classical states
- On the power of one-way automata with quantum and classical states
- Quantum finite automata with control language
- Size lower bounds for quantum automata
- Title not available (Why is that?)
- Exponentially more concise quantum recognition of non-RMM regular languages
- On the state complexity of semi-quantum finite automata
- Characterizations of one-way general quantum finite automata
Cited In (9)
- On the state complexity of semi-quantum finite automata
- On the state complexity of semi-quantum finite automata
- Size lower bounds for quantum automata
- Finite automata capturing winning sequences for all possible variants of the \(PQ\) penny flip game
- On hybrid models of quantum finite automata
- Lower Bounds for Generalized Quantum Finite Automata
- Size lower bounds for quantum automata
- Title not available (Why is that?)
- Application of distributed semi-quantum computing model in phase estimation
This page was built for publication: Lower bounds on the size of semi-quantum finite automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q264532)
