EPSRC Reference: 
EP/G049416/1 
Title: 
New directions in quantum algorithms 
Principal Investigator: 
Montanaro, Professor A 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Computer Science 
Organisation: 
University of Bristol 
Scheme: 
Postdoc Research Fellowship 
Starts: 
01 October 2009 
Ends: 
31 July 2010 
Value (£): 
209,027

EPSRC Research Topic Classifications: 
Fundamentals of Computing 
New & Emerging Comp. Paradigms 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
Quantum computation is a new model of computing based on the principles of quantum mechanics. Excitingly, it offers the prospect of obtaining faster algorithms for certain problems than are possible in classical (ie. nonquantum) computation.As an example, it is believed that there exists no efficient classical algorithm for the task of decomposing a large composite number into its prime factors. This problem is important in cryptography. However, there does exist an efficient quantum algorithm for this task (known as Shor's algorithm). The problem appears to contain some structure that quantum computation can use in a way that classical computation cannot. Another important quantum algorithm is known as Grover's algorithm; surprisingly, using this algorithm a quantum computer can achieve a speedup over classical computers in the basic task of searching an unsorted list.The aim of this research is to develop new quantum algorithms based on different principles to these two algorithms, and conversely to improve our understanding of the limitations of quantum computing. Specific goals of the project are:1. To obtain new quantum speedups by extending classical heuristics to quantum algorithms. The vast majority of research in quantum computing has considered worstcase measures of complexity. This project aims to develop quantum algorithms that outperform classical algorithms on average. This should vastly increase the range of problems to which quantum computers can be usefully applied.2. To initiate a quantum theory of inapproximability of optimisation problems. It is known that it is hard for standard computers to approximate the answer to certain optimisation problems. This project will take the first steps in translating this concept to quantum computation, and will thus prove limitations on the power of quantum computers.3. To produce the first efficient quantum data structures. This project will investigate the question of whether quantum states can be used as data structures to achieve a reduction in space compared to classical data structures.Largescale quantum computers are yet to be built. However, a better understanding of the potential of these machines could both greatly accelerate their development, and give additional reasons for attempting to build them in the first place. This research aims to help produce such an understanding.

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 