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.

This project, if funded, will result in the development of new quantum algorithms, communication protocols and data structures with significant quantifiable advantages over classical computation, and a better understanding being gained of the limitations of quantum computers to solve key problems in quantum physics. In the immediate future, this research will have direct impact on other research workers in the field of quantum computation and also on the security services, who take a keen interest in the potential of quantum computation. In particular, planned collaboration with experimental quantum computing researchers will lead to fast implementation on real quantum computing hardware of the algorithms developed, and the creation of motivating applications for new developments in experimental quantum technology. The international field of quantum computation encompasses computer science, mathematics and physics, and its strongly interdisciplinary nature leads to wide dissemination of results across the globe and immediate worldwide impact in all these fields.

In the medium to long term, the development of new quantum algorithms has the potential to lead to dramatic practical benefits for society. Today's world is algorithmic, as evidenced by the great success of companies such as Google and Yahoo! which are fundamentally dependent on efficient algorithms. The development of Shor's factoring algorithm (perhaps the most famous result in quantum computing) has led to a major upheaval in the world of cryptography, and future advances in quantum computing have the potential for similar levels of impact. For example, one component of this project will produce super-efficient quantum algorithms for testing properties of massive data sets, which will be of use to the many commercial organisations whose businesses are built on huge databases. Another component will develop quantum communication protocols and data structures with significant efficiency improvements over classical computers, which could lead to networked devices requiring fewer resources than previously possible. In yet another direction, this project will produce more efficient quantum algorithms for fundamental tasks in quantum physics and chemistry. Improved simulation of quantum mechanical systems by quantum computing could lead to advances in drug design and the development of novel materials, with lasting benefits for the general public.

Once large-scale quantum computers are built, algorithms, communication protocols and data structures developed now will become indispensable: an eventual quantum computing industry will rely on the foundational theoretical work carried out now to solve the problems of tomorrow. Technologies based on early quantum algorithmic ideas, such as improved quantum metrology, high-precision photodetectors and quantum control, are now approaching commercialisation, and new quantum algorithms developed during this project will lead to the development of future such technologies.

By elucidating the nature of computation in our universe, and the effect of quantum mechanics on computing power, this research will also lead to a deeper philosophical understanding of the world which we inhabit. Such an understanding is harder to quantify but likely to lead to lasting societal benefits.