QnTM: Quantum Speed-up of Classical Algorithms

在解决因式分解问题时，Peter Shor说明，使用量子力学原理的新型计算机的效率可能远远超过今天的计算机。从那时起，量子计算机科学家一直专注于寻找一组计算问题，在那里可以获得如此巨大的加速。本提案的目标是使用两种不同的方法对这个问题进行系统的研究。第一种方法是基于PI早期的工作，他在那里证明了量子行走的过程(即通过对经典算符进行量化而重复使用一个量子算符)可以用来加速一大类经典算法。该提案描述了一种新的量子行走，它可以比以前的量子行走解决更多的问题，并实现更大的加速。这个主题包括许多开放的问题，PI和他的学生们希望研究这些问题。第二种方法与黑盒模型有关，该模型通过找出量子算法必须使用不同的子例程多少次来捕捉它的速度。目前，这个模型已被证明是全面研究量子算法的最成功的工具，而且往往是它们复杂性的忠实指示器。PI之前在黑匣子模型上的工作在量子计算界是众所周知的。该提议提出了几个新的研究思路，旨在更好地理解黑匣子模型。量子计算的研究努力经常导致关于经典算法的有趣发现，这是计算理论中意想不到的新发展。在研究上述两种方法的同时，PI和他的学生计划密切关注这一新的好处。PI目前正在新泽西州立大学罗格斯大学建立一个量子计算小组。几名有兴趣的研究生和本科生已经与国际和平研究所接洽，几位同事也表示，他们愿意参与这样一个小组的研究工作。PI得到了院长和DIMAC的支持，并与朗讯技术公司贝尔实验室和NEC的量子小组建立了合作伙伴关系。学生研究助学金主要需要来自国家科学基金会的支持。

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.