New directions in quantum algorithms
Lead Research Organisation:
University of Cambridge
Department Name: Applied Maths and Theoretical Physics
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
Harrow A
(2013)
Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization
in Journal of the ACM
Montanaro A
(2013)
Weak Multiplicativity for Random Quantum Channels
in Communications in Mathematical Physics
Montanaro A
(2012)
Some applications of hypercontractive inequalities in quantum information theory
in Journal of Mathematical Physics
Montanaro A
(2013)
On Exact Quantum Query Complexity
in Algorithmica
| Description | This research was concerned with the theory of quantum computation and quantum information. On the computational side, I developed new algorithms for quantum computers which show speed-ups over any possible algorithm running on a standard ("classical") computer, and succeed with certainty. These were the first new speed-ups shown in the exact setting for over a decade. Some of these new algorithms were found with the use of a computer; this work thus also showed that interesting new quantum algorithms could be found via numerical search. On the informational side, my research took a step towards a proof that, for almost all quantum communication channels, quantum entanglement does not help too much to achieve a higher communication rate. This provided a counterpoint to recent surprising work which showed that quantum entanglement can provide a small advantage. Finally, my work also considered the mathematical foundations of quantum information theory. In particular, I gave some new applications of a powerful mathematical theory, known as hypercontractivity, in quantum information. These gave new insight into the role this theory might play, and motivation for future research in this area. |
| Exploitation Route | My findings have already been used and extended by a number of workers in the field of quantum computation. For example, my research on exact quantum algorithms gave the first speedup over classical algorithms in this setting for over a decade. Subsequent work by other authors has now shown that exact quantum algorithms can achieve a larger, asymptotic speedup over classical algorithms. Also, my research on hypercontractivity has motivated a significant quantity of subsequent work in pure mathematics, based around improving the parameters of certain bounds in this area. |
| Sectors | Chemicals,Digital/Communication/Information Technologies (including Software),Electronics,Energy,Pharmaceuticals and Medical Biotechnology,Security and Diplomacy |
| Description | This research was on a theoretical topic within the futuristic field of quantum computing, and its full impact beyond academia will therefore be realised on longer timescales. Nevertheless, this research is already affecting the world beyond academia: for example, following the findings of this project I was recently invited to participate in a Turing Gateway workshop bringing industrial and academic partners together to discuss the impact of quantum computing on cryptography. The full eventual impact (both industrial and societal) of this work is expected to be substantial, as it feeds into the overarching question of understanding the power and limitations of quantum computing. |
| First Year Of Impact | 2014 |
| Sector | Security and Diplomacy |
| 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 |