量子计算复杂性与经典计算复杂性的关系

自1980年以来，量子信息学已经发展成为一个具有相当规模和科学基础的交叉学科。特别是1994年Shor提出的大数分解的量子多项式时间算法，使得量子计算成为当今理论计算机科学中最热门的方向之一。探索量子算法的优势极限，是当今亟待解决的重大科学问题。我们计划对量子复杂性和经典复杂性之间的关系进行研究。在量子查询复杂性模型中，已经证明Grover搜索算法(运行时间sqrt(n))是最优的，也就是说量子数据库查找算法最多能够比经典算法有平方量级的加速。学者普遍认为这一结论对于任何total function都成立。这一猜想需要我们能提出新的证明量子查询复杂性下限的方法。我们计划从一些具体的函数例子出发，例如我们计划研究：在网格上的local search的量子算法下限。通信复杂性是另外一个重要的模型，我们也将研究这一模型下量子复杂性和经典复杂性的关系。