New insights in quantum algorithms and complexity

Lead Research Organisation: University of Bristol
Department Name: Mathematics

Abstract

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. Large-scale 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, super-efficient 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 speed-ups 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 large-scale 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.

Planned Impact

This project, if funded, will result in the development of new quantum algorithms, communication protocols and data structures with significant quantifiable advantages over classical computation, and a better understanding being gained of the limitations of quantum computers to solve key problems in quantum physics. In the immediate future, this research will have direct impact on other research workers in the field of quantum computation and also on the security services, who take a keen interest in the potential of quantum computation. In particular, planned collaboration with experimental quantum computing researchers will lead to fast implementation on real quantum computing hardware of the algorithms developed, and the creation of motivating applications for new developments in experimental quantum technology. The international field of quantum computation encompasses computer science, mathematics and physics, and its strongly interdisciplinary nature leads to wide dissemination of results across the globe and immediate worldwide impact in all these fields.

In the medium to long term, the development of new quantum algorithms has the potential to lead to dramatic practical benefits for society. Today's world is algorithmic, as evidenced by the great success of companies such as Google and Yahoo! which are fundamentally dependent on efficient algorithms. The development of Shor's factoring algorithm (perhaps the most famous result in quantum computing) has led to a major upheaval in the world of cryptography, and future advances in quantum computing have the potential for similar levels of impact. For example, one component of this project will produce super-efficient quantum algorithms for testing properties of massive data sets, which will be of use to the many commercial organisations whose businesses are built on huge databases. Another component will develop quantum communication protocols and data structures with significant efficiency improvements over classical computers, which could lead to networked devices requiring fewer resources than previously possible. In yet another direction, this project will produce more efficient quantum algorithms for fundamental tasks in quantum physics and chemistry. Improved simulation of quantum mechanical systems by quantum computing could lead to advances in drug design and the development of novel materials, with lasting benefits for the general public.

Once large-scale quantum computers are built, algorithms, communication protocols and data structures developed now will become indispensable: an eventual quantum computing industry will rely on the foundational theoretical work carried out now to solve the problems of tomorrow. Technologies based on early quantum algorithmic ideas, such as improved quantum metrology, high-precision photodetectors and quantum control, are now approaching commercialisation, and new quantum algorithms developed during this project will lead to the development of future such technologies.

By elucidating the nature of computation in our universe, and the effect of quantum mechanics on computing power, this research will also lead to a deeper philosophical understanding of the world which we inhabit. Such an understanding is harder to quantify but likely to lead to lasting societal benefits.

Publications

10 25 50
 
Description This project aims to find new applications for quantum computers, and to produce a better understanding of their power. The project is still ongoing, but the major results obtained so far are as follows. First, I have developed many new algorithms for quantum computers which outperform their classical counterparts. These include a quantum algorithm which speeds up the ubiquitous classical technique known as backtracking for solving constraint satisfaction problems, and a quantum algorithm for accelerating "Monte Carlo methods", which are based on the use of randomness to estimate quantities of interest. In a separate programme of research, together with collaborators Cubitt and Piddock I have classified the computational power of various natural classes of physical systems ("Hamiltonians"). Applying computational complexity theory to physics in this way has led to new insights into the complexity of these systems, and into the power of quantum simulators. In a third programme, together with Bremner and Shepherd I have shown that (subject to certain computational complexity conjectures) a particularly simple class of quantum circuits is hard to simulate classically. This has already led to over 50 follow-up works in this area. Recent hirings on this grant (Ryan Mann and Changpeng Shao) have broadened the aspects of quantum computing considered on the grant, to include topics relating to combinatorics and machine learning.
Exploitation Route There are two natural ways to take forward the theoretical results of this project: experimental implementations of the algorithms and algorithmic techniques developed, in collaboration with experimental quantum computing researchers (or via a cloud-based quantum computing provider); and consultancy with industry to determine the feasibility of applying this work to their pressing problems. I have begun exploring both of these directions myself, via the quantum software startup Phasecraft that I cofounded.
Sectors Aerospace, Defence and Marine,Agriculture, Food and Drink,Digital/Communication/Information Technologies (including Software),Electronics,Energy,Manufacturing, including Industrial Biotechology,Pharmaceuticals and Medical Biotechnology,Transport

 
Description I recently cofounded a quantum software startup company, PhaseCraft, together with Toby Cubitt and John Morton. This company aims to develop software for quantum computers, building on my expertise developed during this Fellowship. I am also a founding consultant of Q&I, a consultancy organisation set up to provide expert advice to businesses on the impact of quantum computing; clients thus far have included a major energy industry firm. My work has also led to a number of further interactions with industry at workshops as an invited speaker, providing expertise on applications of quantum computing. For example, I was an invited participant at a Knowledge Transfer Network workshop on quantum technologies in finance (2016), two Turing Gateway events on post-quantum cryptography (2014), and took part in a Turing Gateway event on Algorithms and Software for Quantum Computers in 2018. I participated in an InnovateUK project on applications of quantum computing to the telecommunications industry, with industrial partners BT, D-Wave and Plantagenet Systems. I have been interviewed for articles about my work in the Washington Post (2019), Wired (2019), IET's Engineering and Technology magazine (2016), Gizmodo and Quanta (2017), and my work has been covered in Forbes (2017).
Sector Aerospace, Defence and Marine,Digital/Communication/Information Technologies (including Software),Energy
Impact Types Economic,Policy & public services

 
Description Submission and presentation to select committee inquiry
Geographic Reach National 
Policy Influence Type Gave evidence to a government review
URL https://www.parliament.uk/business/committees/committees-a-z/commons-select/science-and-technology-c...
 
Description (QAFA) - Quantum Algorithms from Foundations to Applications
Amount € 1,859,312 (EUR)
Funding ID 817581 
Organisation European Commission 
Sector Public
Country European Union (EU)
Start 04/2019 
End 04/2024
 
Title Data from "Quantum speedup of branch-and-bound algorithms" 
Description Source code and experimental results for the paper "Quantum speedup of branch-and-bound algorithms" by Ashley Montanaro. 
Type Of Material Database/Collection of data 
Year Produced 2019 
Provided To Others? Yes  
URL https://data.bris.ac.uk/data/dataset/2lp4ih2gs5o2w1yntjca3e3il7/
 
Title Data from "Simulating Quantum Computations with Tutte Polynomials" 
Description Source code and experimental data for the paper "Simulating Quantum Computations with Tutte Polynomials" by Ryan L. Mann. 
Type Of Material Database/Collection of data 
Year Produced 2021 
Provided To Others? Yes  
Impact Source code and experimental data for the paper "Simulating Quantum Computations with Tutte Polynomials" by Ryan L. Mann. 
URL https://data.bris.ac.uk/data/dataset/kbhgclva863q21tjkqpyr5uvq/
 
Title Data from Quantum algorithms for CSPs (07-2019) 
Description Quantum algorithms can deliver asymptotic speedups over their classical counterparts. However, there are few examples known where a substantial quantum speedup has been worked out in detail for reasonably-sized problems, when compared with the best classical algorithms and taking into account realistic hardware parameters and overheads for fault-tolerance. All known examples of such speedups correspond to problems related to simulation of quantum systems and cryptography. In this project we apply general-purpose quantum algorithms for solving constraint satisfaction problems to two families of prototypical NP-complete problems: boolean satisfiability and graph colouring. We consider two quantum approaches: Grover's algorithm and a quantum algorithm for accelerating backtracking algorithms. The data stored in the repository is numerical results from computational experiments, as well as corresponding source code. 
Type Of Material Database/Collection of data 
Year Produced 2019 
Provided To Others? Yes  
 
Title Source code and experimental results from Applying quantum algorithms to CSPs (10-2018) 
Description Quantum algorithms can deliver asymptotic speedups over their classical counterparts. However, there are few examples known where a substantial quantum speedup has been worked out in detail for reasonably-sized problems, when compared with the best classical algorithms and taking into account realistic hardware parameters and overheads for fault-tolerance. All known examples of such speedups correspond to problems related to simulation of quantum systems and cryptography. In this project we apply general-purpose quantum algorithms for solving constraint satisfaction problems to two families of prototypical NP-complete problems: boolean satisfiability and graph colouring. We consider two quantum approaches: Grover's algorithm and a quantum algorithm for accelerating backtracking algorithms. The data stored in the repository comprises numerical results from computational experiments, as well as corresponding source code. 
Type Of Material Database/Collection of data 
Year Produced 2018 
Provided To Others? Yes  
 
Description Collaboration by Ryan Mann with Catherine Greenhill (UNSW) and Luke Mathieson (UTS) 
Organisation University of New South Wales
Country Australia 
Sector Academic/University 
PI Contribution Dr. Luke Mathieson (University of Technology Sydney), Professor Catherine Greenhill (University of New South Wales), and Dr. Ryan Mann have been collaborating on a research paper, with a draft manuscript prepared.
Collaborator Contribution Dr. Luke Mathieson (University of Technology Sydney), Professor Catherine Greenhill (University of New South Wales), and Dr. Ryan Mann have been collaborating on a research paper, with a draft manuscript prepared.
Impact The work was accepted for a talk at the 42nd Australasian Conference on Combinatorial Mathematics and Combinatorial Computing (ACCMCC) and was presented by Dr. Luke Mathieson.
Start Year 2019
 
Description Collaboration by Ryan Mann with Catherine Greenhill (UNSW) and Luke Mathieson (UTS) 
Organisation University of Technology Sydney
Country Australia 
Sector Academic/University 
PI Contribution Dr. Luke Mathieson (University of Technology Sydney), Professor Catherine Greenhill (University of New South Wales), and Dr. Ryan Mann have been collaborating on a research paper, with a draft manuscript prepared.
Collaborator Contribution Dr. Luke Mathieson (University of Technology Sydney), Professor Catherine Greenhill (University of New South Wales), and Dr. Ryan Mann have been collaborating on a research paper, with a draft manuscript prepared.
Impact The work was accepted for a talk at the 42nd Australasian Conference on Combinatorial Mathematics and Combinatorial Computing (ACCMCC) and was presented by Dr. Luke Mathieson.
Start Year 2019
 
Description Collaboration with Aram Harrow, MIT 
Organisation Massachusetts Institute of Technology
Department Department of Physics
Country United States 
Sector Academic/University 
PI Contribution Dr Aram Harrow from MIT and I have collaborated on several papers and ongoing research directions during this project.
Collaborator Contribution Dr Aram Harrow from MIT and I have collaborated on several papers and ongoing research directions during this project.
Impact Thus far, two completed (and not yet published) papers have resulted from this collaboration, as well as one invited survey paper.
Start Year 2014
 
Description Collaboration with Michael Bremner, UTS Sydney 
Organisation University of Technology Sydney
Department Biochemistry and Cellular and Molecular Biology
Country Australia 
Sector Academic/University 
PI Contribution Prof Michael Bremner and I have collaborated on two research papers, one of which is now complete (and published in Physical Review Letters), the other of which is under review.
Collaborator Contribution Prof Michael Bremner and I have collaborated on two research papers, one of which is now complete (and published in Physical Review Letters), the other of which is under review.
Impact A paper published in Physical Review Letters, and another paper under review.
Start Year 2014
 
Description Collaboration with Tyler Helmuth, Durham University (2019 - Still Active) 
Organisation Durham University
Department Department of Mathematical Sciences
Country United Kingdom 
Sector Academic/University 
PI Contribution Prof Tyler Helmuth and I have collaborated on one research paper (and published in the Journal of Mathematical Physics). We are currently working on another project.
Collaborator Contribution Prof Tyler Helmuth and I have collaborated on one research paper (and published in the Journal of Mathematical Physics). We are currently working on another project.
Impact A paper published in the Journal of Mathematical Physics.
Start Year 2019
 
Company Name PHASECRAFT LIMITED 
Description PhaseCraft is a quantum software company that aims to develop software for near-term quantum computers. The company was founded by Ashley Montanaro (University of Bristol), Toby Cubitt and John Morton (UCL). 
Year Established 2018 
Impact PhaseCraft was founded in 2018, completed its first investment round in early 2019, and employs 2 full-time staff, as well as supporting 3 PhD students. The company is currently focused on early-stage technology development.
 
Description Bristol Futurists talk 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach Local
Primary Audience Public/other audiences
Results and Impact I gave a public talk on quantum computing to the "South West Futurists" group in February 2016, together with a member of the Centre for Quantum Photonics. This was the group's most popular talk so far, with over 50 attendees, and was streamed live on YouTube. Attendees afterwards rated the talk as 5* on the group's website.
Year(s) Of Engagement Activity 2016
URL http://www.meetup.com/South-West-Futurists/events/227738946/
 
Description London Quantum Computing Meetup 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Public/other audiences
Results and Impact I gave a public talk at UCL in London, attended by over 120 members of the public, and followed by a full hour of questions from the audience. The talk received excellent feedback.
Year(s) Of Engagement Activity 2017
 
Description Meeting about quantum computing in finance 
Form Of Engagement Activity A formal working group, expert panel or dialogue
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Industry/Business
Results and Impact I participated in a 'market-focused' innovation workshop that explored future commercial uses of quantum technologies within the finance sector, with support from the Knowledge Transfer Network and InnovateUK. The purpose of the workshop was to determine the most promising business uses for QT within this sector, report on key market-focused aspects (e.g. potential market size, timelines, enablers and barriers) and determine the level of interest in them from key stakeholders. The workshop involved not only quantum technology developers (academia and industry), but also potential end-users from this market, who helped to validate the best business cases.
Year(s) Of Engagement Activity 2016
 
Description Turing Gateway events 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Industry/Business
Results and Impact I was invited to speak at two Turing Gateway events, organised by GCHQ, on the subject of post-quantum cryptography. These workshops were targeted at academic and industrial attendees as well as government, and fed into the government's strategy on building quantum-secure cryptosystems.
Year(s) Of Engagement Activity 2014