New insights in quantum algorithms and complexity

点击翻译按钮获取中文摘要

A quantum computer is a machine built to use the mysterious principles of quantum mechanics to achieve an advantage in some task over any standard ("classical") computer. Large-scale quantum computers have not yet been built; however, an international effort is currently underway to do so. Much theoretical work has also been carried out to understand the power of quantum computation, and in particular, quantum algorithms have been developed for certain problems that outperform any possible algorithm running on a classical computer. These problems include breaking cryptographic codes (such as the RSA code which underlies Internet security), certain database search problems, and efficient simulation of quantum mechanical systems (with applications including design of medicinal compounds and novel materials).One reason that the study of quantum computing is so fascinating is that, as well as having practical applications like this, it enables us to obtain a deeper understanding of nature. As it appears that quantum mechanics is the physical theory on which our universe is based, understanding what a quantum computer can do is nothing less than understanding the computational power of the universe.This project aims to find a deeper understanding of what it is about certain problems which means that there is an efficient quantum algorithm to solve them. In particular, the project will develop new algorithms and protocols for quantum computers to obtain dramatic efficiency improvements over classical computation. Some of these algorithms could be tested experimentally in the near future. The proposal is divided into three themes.The first theme will find new quantum algorithms, communication protocols and data structures. For example, super-efficient quantum algorithms will be developed for determining whether an object has some property, or is very far away from having that property. One problem of this nature would be to determine whether a computer network is connected or very far from connected, by looking at only a few, randomly chosen, links between computers. It is by now fairly well understood which problems like this have fast solutions on a classical computer. However, quantum computers might be able to achieve dramatic speed-ups for certain problems of this type. Efficient algorithms for discrete problems (e.g. concerning graphs and codes) will also be developed using the exciting new technique known as quantum walks, and finally the question of whether there exist quantum data structures which are more efficient than any classical data structure will be attacked.In the second theme, ideas from quantum computing will be used to study the complexity of problems from quantum physics and quantum chemistry. On the one hand, new quantum algorithms will be developed that allow quantum computers to solve practically important problems from these fields more efficiently than is possible classically. On the other, intractability of certain problems in this area will be proven, which will enable practitioners (such as physicists and chemists) to determine when problems they want to solve are actually intrinsically hard. Ideas from quantum computing are thus a helpful tool even without having access to a large-scale quantum computer.Finally, the third theme will develop new underlying mathematical technology in order to solve the difficult problems thrown up by the first two themes. These include developments in the theory of "hypercontractivity", which has recently been an essential tool in many important results in theoretical computer science, and new mathematical techniques to find tighter bounds on the abilities of quantum computation.Taken together, these results will mark a significant leap forward in our understanding of the power of quantum computers.