QnTM: Quantum Speed-up of Classical Algorithms

在解决因式分解问题时，彼得·肖尔（Peter Shor）举例说明了一种使用量子力学原理的新型计算机可能远远超过当今计算机的效率。从那时起，量子计算机科学家一直专注于寻找可以获得这种量级的加速的计算问题。目前的建议旨在使用两种不同的方法对这个问题进行系统的研究。第一种方法是基于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.