EPSRC logo

Details of Grant 

EPSRC Reference: EP/G049416/1
Title: New directions in quantum algorithms
Principal Investigator: Montanaro, Dr A
Other Investigators:
Researcher Co-Investigators:
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:
Panel DatePanel NameOutcome
13 Feb 2009 Postdoc Fellowships 2009 in Comp. Science - Sift Excluded
11 Mar 2009 Postdoc. Fellowships Interviews - Computer Science Announced
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. non-quantum) 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 speed-up 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 speed-ups by extending classical heuristics to quantum algorithms. The vast majority of research in quantum computing has considered worst-case 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.Large-scale 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 non-academic 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