量子有穷自动机的时空复杂度优势及相关问题

An important way to get a deeper insight into the power of quantum computing is to explore the simplest model of quantum computing-quantum finite automata. There are a lot results on time complexity and state complexity (space complexity) of quantum finite automata so far. However, all these results are on time or space complexity alone, there is not any result that considers simultaneously both. In this project, we investigate first time the time-space complexity of two-way quantum finite automata. (1) We will try to prove that two-way quantum finite automata have advantages on time-space complexity comparing to their classical counterparts in recognizing languages. (2) It has been proved (Klauck, STOC'00) that the exact one-way quantum finite automata have no advantage comparing to classical finite automata in recognizing languages. It is open for many years that whether exact two-way quantum finite automata have advantages comparing to their classical counterparts in recognizing languages or not. In this project, we will try to solve the open problem and prove that exact two-way quantum finite automata do have advantages in time-space complexity. (3) Time-space complexity is related with communication complexity and quantum communication is related with quantum query complexity. In order to prove the time-space advantages of two-way quantum finite automata, this project will also study some related problems on quantum communication complexity and quantum query complexity.

量子有穷自动机作为量子计算最简单的模型，对它的研究有利于对量子计算本质的理解。 迄今量子有穷自动机在时间、状态复杂度（空间复杂度）方面都有许多的工作，但是学者们都是单独考虑其时间复杂度或者空间复杂度。本项目主要研究：（1）从一个新的角度即时空复杂度的角度去研究双向量子有穷自动机。尝试去证明在识别一些语言时，双向量子有穷自动机相对于双向经典有穷自动机有优势。（2）早在2000年，Klauck(STOC’00)就证明了精确（没有误差）单向量子有穷自动机在识别语言时相对于单向经典有穷自动机没有任何的优势，而精确双向量子有穷自动机跟双向经典有穷自动机比是否有优势，一直是这个领域公开的问题。本项目将从时空复杂度去证明其优势，致力于解决这一公开问题。（3）时空复杂度往往跟通信复杂度有联系，而量子通信复杂跟量子查询复杂度有关系，所以本项目也开展这两方面相关的研究，为证明时空复杂度作准备。

量子有穷自动机作为量子计算最简单的模型，对它的研究有利于对量子计算本质的理解。 .迄今量子有穷自动机的时间、状态复杂度（空间复杂度）都有许多的工作，但是学者们都是 单独考虑其时间复杂度或者空间复杂度。本项目主要研究：主要研究量子有穷自动的时空复杂度优势和与量子通信复杂跟量子查询复杂度的关系。本项目的主要成果如下：1）证明了双向量子有穷自动机与双向概率自动机相比在时空复杂度上是有优势的。结果发表在国际权威SCI期刊Theoretical Computer Science，2）推广了知名的Deutsch-Jozsa约束性问题的结论，提出和研究汉明权重区别问题。在Deutsch-Jozsa约束性问题中，讨论的是区分输入的汉明权重是{0,n}还是{n/2}. 本项目将结论推广到区分输入的汉明权重是{0,1,...,k, n-k,…,n}还是{n/2}，并给出了最优的精确查询量子算法。同时，本人还将该结果推广到量子查询复杂度和自动机状态复杂度的对应问题上。部分的论文成果发表在Physical Review A上。3）证明精确单向量子有穷自动机在解决约束性问题上有状态复杂性的优势，并在光学实验室上验证该结论, 论文成果发表在npj Quantum Information上。4）刻画了一次精确量子查询算法能解决的所有对称偏函数。相关结果我们也在17th Asian Quantum Information Science Conference的国际会议上做了口头报告。本项目一共发表SCI论文12篇，参加会议14次。