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.
