New directions in quantum algorithms
Lead Research Organisation:
University of Bristol
Department Name: Computer Science
Abstract
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.
People |
ORCID iD |
| Ashley Montanaro (Principal Investigator) |
Publications
Montanaro A
(2010)
Nonadaptive quantum query complexity
in Information Processing Letters
Harrow A
(2011)
Automata, Languages and Programming
Ashley Montanaro (Author)
(2011)
A new exponential separation between quantum and classical one-way communication complexity
in Quantum Information & Computation
Montanaro A
(2011)
Unbounded-error quantum query complexity
in Theoretical Computer Science
Montanaro A
(2011)
Theory of Quantum Computation, Communication, and Cryptography
Clifford R
(2011)
The Complexity of Flood Filling Games
in Theory of Computing Systems
Montanaro A
(2012)
The quantum query complexity of learning multilinear polynomials
in Information Processing Letters
| Description | This project has led to multiple and diverse new developments in our understanding of the power of quantum computers, and how they can outperform any possible standard ("classical") computer. First, new quantum algorithms and communication protocols have been developed for several tasks which are significantly more efficient than any possible classical algorithm. One example is search of an unstructured list where there is some prior information about the input; a new quantum algorithm has been developed which can achieve exponential speed-ups on average. This demonstrates that there are simple and natural problems for which quantum computers can achieve dramatic advantages. Another example is a newly developed quantum communication protocol which demonstrates an exponential reduction in communication over any possible classical protocol. This result will feed in to the development of quantum data structures which outperform classical data structures. In another direction, an important result of the project was the development of an efficient test for the fundamental question of whether a multipartite quantum state is unentangled. This test has already found numerous applications. One of the most important of these (also developed during this project) is a proof of the long-standing conjecture that multiple-prover quantum proof systems can be simulated by two provers. Surprisingly, the resolution of this seemingly obscure question turns out to allow computational hardness to be proven for a number of natural tasks within quantum information theory and elsewhere. Examples of such tasks include testing separability of quantum states, and well-studied tensor optimisation problems from classical computer science. Finally, foundational research into quantum information theory and its underlying mathematics, as well as the origin of the power of quantum computers, has been carried out throughout the project. For example, one of the most natural settings in which quantum computers outperform classical computers is query complexity (where the quantity of interest is the number of queries to the input required to compute some function). This project completely characterised two different special cases (nonadaptive and unbounded-error) of the quantum query complexity model. The new applications and techniques developed during this project have already inspired a number of follow-on works, and are likely to lead to many more. |
| Exploitation Route | When large-scale quantum computers are developed, it is likely that as well as their academic applications, they will be widely used in industry and throughout society. Examples of results from this project which would be of industrial use include the unstructured quantum search algorithm developed (which could be of use to any large organisation faced with the task of searching a massive data set) and the test for multipartite entanglement. As a subroutine running as part of a quantum simulation package, this would be of use to companies in any field where quantum mechanical modelling is required (such as drug discovery). When a large-scale quantum computer is developed, the algorithms and protocols developed in this project will be run on such a computer, significantly accelerating the solution of problems for which there is no efficient solution on a standard computer. There are numerous potential applications: in particular, the algorithm for search of an unstructured list with prior information on the input could be used to speed up almost any database search application, and the test for multipartite entanglement would be a crucial component of a simulator of quantum mechanical systems. The development of new quantum algorithms provides essential motivatation for the construction of experimental quantum computers, which in turn lead to spin-off technological developments. In the more immediate future, the computational hardness results proven as part of the project are useful to researchers working on optimisation problems, even those that have no apparent connection to quantum computing. |
| Sectors | Digital/Communication/Information Technologies (including Software),Electronics,Pharmaceuticals and Medical Biotechnology |
| Description | This research has led to substantial advances in the field of quantum computation, in a number of directions. These are outlined below. This research has significantly contributed to our understanding of the power of quantum computers, in a number of different ways, some selected examples of which follow. First, new quantum algorithms were developed for the natural problem of searching an unstructured list with a prior probability distribution on the location of the sought item, demonstrating that quantum computers can solve this problem exponentially more quickly (on average) than any possible standard computer. Second, an efficient test was given for the fundamental problem of whether a multipartite quantum system is unentangled. Using this test, it was demonstrated that multi-prover quantum proofs can be simulated by only two provers. This result, which settled a long-standing open problem in quantum computing, in turn has found many applications by other authors in the field. Surprisingly, the result was also used to prove computational hardness of a number of natural optimisation tasks, many of which have no apparent connection to quantum computing. Third, a new example was given of a communication problem which quantum computers can solve with exponentially less communication than standard computers. This example was a more natural problem than was previously known. The final example we discuss here is a tangential work: developing a collaboration with classical computer scientists, the complexity of the popular combinatorial game known as "Flood-It" was analysed. As well as being highlighted on popular-science websites, this work has led to several spin-off mathematical developments. Beneficiaries: Researchers within the field of quantum computing and elsewhere Contribution Method: The research improved to our understanding of the power and limitations of quantum computers. By giving new algorithms and communication protocols for tasks at which quantum computers can dramatically outperform any possible classical computer, and simultaneously developing new lower bounds helping to characterise the tasks for which quantum computers have an advantage, the research has significantly contributed to the theory of quantum computation. The timeliness and interest of the project is demonstrated by, for example, the numerous international invited talks that have been given about the research. |
| First Year Of Impact | 2014 |
| Sector | Security and Diplomacy |
| Impact Types | Economic |
| Description | Collaboration with Aram Harrow, University of Washington |
| Organisation | University of Washington |
| Country | United States |
| Sector | Academic/University |
| PI Contribution | A bilateral collaboration with Dr Aram Harrow from the University of Washington which resulted in the two papers "An efficient test for product states, with applications to quantum Merlin-Arthur games" and "Limitations on quantum dimensionality reduction". Dr Aram Harrow is acknowledged as a leading expert in quantum information theory. Some of the most important achievements of this project came from collaboration with Dr Harrow. In particular, the collaborative work "An efficient test for product states, with applications to quantum Merlin-Arthur games", which was presented at the prestigious FOCS'10 conference, could not have been completed without Dr Harrow's input. |
| Start Year | 2009 |
| Description | Collaboration with Japanese computer scientists |
| Organisation | Osaka Prefecture University |
| Country | Japan |
| Sector | Academic/University |
| PI Contribution | A collaboration with two researchers from Osaka Prefecture University and IBM Research, Japan, which led to the work "Unbounded error quantum query complexity". Following a serendipitous meeting at a conference, a collaboration with Dr Harumichi Nishimura from Osaka Prefecture University and Dr Rudy Raymond from IBM Research, Japan led to the work "Unbounded error quantum query complexity". All three authors made essential contributions to this work. |
| Start Year | 2009 |
| Description | Collaboration with computer scientists, University of Bristol |
| Organisation | University of Bristol |
| Country | United Kingdom |
| Sector | Academic/University |
| PI Contribution | A new collaboration with several classical computer scientists at the University of Bristol which led to the analysis of a popular combinatorial game. A productive collaboration with several classical computer scientists at the University of Bristol led to the analysis of the popular combinatorial game "Flood-It", work which sparked some interest in the media. |
| Start Year | 2009 |
| Description | Unentangled quantum proofs and their applications |
| Form Of Engagement Activity | A magazine, newsletter or online publication |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | |
| Results and Impact | General-interest review article on the topic of entanglement in quantum proof systems for ERCIM News 58 (special issue on unconventional computing paradigms). ERCIM is the European Research Council for Informatics and Mathematics. I was invited to write an article about my research for the general-interest magazine "ERCIM News" for the European Research Consortium for Informatics and Mathematics. |
| Year(s) Of Engagement Activity | 2011 |