Zheng, Shenggen 

Title: On advantages of several exact quantum computing models

Abstract: Quantum computing is one of the most intensively studied research fields in recent years. Quantum computing models can be divided into bounded-error and exact versions in terms of their outputs. In the bounded-error setting, quantum complexity is now relatively well understood. The model of exact quantum computing, where the algorithms must output the correct answer with certainty for every input, seems to be more intriguing. It is much more difficult to come up with exact quantum algorithms that outperform classical exact algorithms. In this talk, we will show some of our newest results on exact quantum computing for several computing models, including query complexity, communication complexity, time-space complexity and state complexity of finite automata.

Publication
1) arXiv:1603.06505 ,
2) Theoretical Computer Science, 666, 48-64 (2017)
3) Mathematical Structures in Computer Science, 27, 311-331 (2017)
4) Time-space complexity advantages for quantum computing, LNCS 10687 05-317
(2017)
5) Exact quantum algorithms have advantage for almost all Boolean functions,
Quantum Information and Computation, 15, 0435-0452 (2015)
6) Potential of quantum finite automata with exact acceptance, International Journal
of Foundation of Computer Science, 26, 381-398 (2015)
7) On the state complexity of semi-quantum finite automata, RAIRO-Inf. Theor. Appl.,
48, 187-207 (2014)
8) From quantum query complexity to state complexity, LNCS, 8808 231-245 (2014).