QnTM: Quantum Speed-up of Classical Algorithms

在解决因式分解问题时，彼得·肖尔说明了一种使用量子力学原理的新型计算机可以远远超过当今计算机的效率。从那时起，量子计算机科学家一直致力于寻找能够获得这种量级加速的计算问题组。本提案的目标是使用两种不同的方法对这个问题进行系统的研究。第一种方法是基于PI早期的工作，在那里他展示了量子行走的过程（即通过“量子化”一个经典算子而重复使用一个量子算子）可以用来加速一大类经典算法。该提案描述了一种新的量子行走，它可以解决比以前更多的问题，并获得更大的加速。这个主题包含许多开放的问题，PI和他的学生希望调查。第二种方法与黑箱模型有关，它通过找出量子算法需要使用不同子程序的次数来捕捉量子算法的速度。目前，该模型已被证明是量子算法综合研究中最成功的工具，通常是其复杂性的忠实指标。PI之前在黑盒模型上的工作在量子计算社区是众所周知的。该提案提出了几个新的研究思路，旨在更好地理解黑箱模型。量子计算的研究工作往往会导致经典算法的有趣发现，这是计算理论的一个意想不到的新发展。在研究上述两种方法的同时，PI和他的学生们计划密切关注这一新的好处。PI目前正在新泽西州立大学罗格斯分校建立一个量子计算小组。研究生和本科生两级的一些感兴趣的学生已经同PI接触，一些同事也表示他们愿意参加这样一个小组的研究工作。PI得到了院长和DIMACS的支持，并与朗讯科技的贝尔实验室和NEC的量子小组建立了合作关系。NSF的支持主要用于学生研究助理。

When solving the factorization problem, Peter Shor illustrated that a new type of computer using principles of quantum mechanics could far exceed the efficiency of today's computers. Since then quantum computer scientists have been focusing on finding the group of computational problems where speed-ups of this magnitude can be obtained. The present proposal targets a systematic study of this question using two different methods.The first method is based on earlier work by the PI, where he showed that the process of quantum walks (i.e. the repeated use of a quantum operator made by "quantizing" a classical operator) can be used to speed up a large class of classical algorithms. The proposal describes new kinds of quantum walks that could solve more problems than previous ones and attain larger speed-ups. This topic comprises many open questions, which the PI and his students wish to investigate.The second method relates to the black box model, which captures the speed of a quantum algorithm by finding out how many times it has to use different subroutines. At present, this model has proved to be the most successful tool in the comprehensive study of quantum algorithms and is often a faithful indicator of their complexities. The PI's previous works on the black box model are well-known in the quantum computing community. The proposal raises several new research ideas that aim at a better understanding of the black box model.Quantum computation research efforts often lead to interesting discoveries about classical algorithms, which is an unexpected new development in the theory of computing. While researching the two methods above, the PI and his students plan to keep a watchful eye on this new benefit.The PI is currently building a quantum computing group at Rutgers, The State University of NJ. The PI has been approached by several interested students both at the graduate and undergraduate levels, and several colleagues have indicated as well that they would be ready to participate in the research efforts of such a group. The PI gained support from the deans and DIMACS, and built partnerships with quantum groups at Lucent Technologies' Bell Labs and NEC. Support from NSF is needed primarily for student research assistantships.