From Quantum Query Complexity to State Complexity

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

ZHENG Shenggen QIU Daowen

Year of publication 2014
Type Article in Proceedings
Conference Computing with New Resources
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1007/978-3-319-13350-8_18
Field Informatics
Keywords General method; Quantum finite automata; Quantum query complexity; Query complexity; State complexity
Description State complexity of quantum finite automata is one of the interesting topics in studying the power of quantum finite automata. It is therefore of importance to develop general methods how to show state succinctness results for quantum finite automata. One such method is presented and demonstrated in this paper. In particular, we show that state succinctness results can be derived out of query complexity results.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.