EPSRC Reference: 
EP/L021005/1 
Title: 
New insights in quantum algorithms and complexity 
Principal Investigator: 
Montanaro, Professor A 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Mathematics 
Organisation: 
University of Bristol 
Scheme: 
EPSRC Fellowship 
Starts: 
31 July 2014 
Ends: 
30 June 2020 
Value (£): 
841,259

EPSRC Research Topic Classifications: 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
04 Feb 2014

EPSRC ICT Responsive Mode  Feb 2014

Announced

10 Mar 2014

ICT Fellowship Interviews Mar 2014

Announced


Summary on Grant Application Form 
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. Largescale 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, superefficient 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 speedups 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 largescale 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.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
http://www.bris.ac.uk 