QuantAlgo: Quantum algorithms and applications

Lead Research Organisation: University of Bristol
Department Name: Mathematics

Abstract

During the 20th century, the development of information technologies had a huge impact not only on science but also on society as a whole. This unprecedented revolution revealed a need to improve the speed and efficiency of data processing, as well as to strive for better security and privacy. One ultimate limitation of current information processing models is that they assume a simplified representation of physics, relying on classical mechanics. Quantum information technologies promise to break this barrier by achieving the highest security and efficiency allowed by the laws of physics, hence leading to a new revolution in information technologies, in the form of a large-scale network of classical and quantum computing devices able to communicate and process massive amounts of data both efficiently and securely using quantum resources. Despite steady experimental progress, we are still far from this longterm vision, not only due to technological limitations but also to the still-narrow range of applications of current quantum algorithms.

The vision of this project is to combine research on the fundamentals of quantum algorithms with the development of new applications targeted at areas of extreme practical importance and timeliness such as big data and machine learning. The project will complement ongoing experimental efforts in quantum technologies by providing new software tools in order to help lead to a revolution in information technologies, harnessing the power of quantum resources to go well beyond today's capabilities, while maintaining a secure digital society.

Planned Impact

Quantum mechanics was developed in Europe a century ago by a generation of now-famous physicists such as Planck, Einstein, Bohr, Heisenberg, Schrödinger, etc. From fundamental research, their discoveries led to a revolution by bringing to modern society disruptive technologies such as lasers, transistors and magnetic resonance imaging. Today, research in quantum technologies gives us a glimpse of a second quantum revolution, with applications such as quantum clocks, quantum sensors, quantum communication links and quantum computers. Many countries around the world are investing heavily in research on quantum technologies in an effort to lead the way in this revolution. In the private sector, leading companies such as Google, Microsoft and IBM have also understood the promises of quantum technologies and therefore opened internal research departments in this area.

To place Europe at the forefront of this second quantum revolution, it is crucial to structure its efforts to create an efficient synergy between all involved players, academic and industrial. Our project could play an important role in this regard by providing key quantum software to exploit future quantum technologies to their fullest capacity. Concretely, while Shor's factoring algorithm was an important motivation for research in quantum computation, one cannot deny that a future quantum computer would be of limited use if all it could do is factorize numbers (especially if in the meantime, we move away from RSA encryption and other cryptographic schemes based on the hardness of factoring). While other applications of quantum algorithms have been found, many of them address abstract mathematical problems, and there are still rather few real-life application areas where quantum algorithms are known to substantially outperform the best classical algorithms. Therefore, new ideas are needed to fully realize the potential of a second quantum revolution. Our project proposes to take an important first step in that direction by providing new quantum algorithms with practical commercial or industrial applications (including e.g. mathematical finance and engineering) and testing them on real data. It is reasonable to believe that the field of quantum algorithms is now ripe for such a challenge, due to the recent development of techniques such as the HHL algorithm, able to provide exponential speed-ups for algebraic problems relevant to practical applications.

Together with future quantum hardware, such applications have the potential to bring transformative advances to science, industry and society.

Publications

10 25 50
publication icon
Alexandru C (2020) Quantum speedups of some general-purpose numerical optimisation algorithms in Quantum Science and Technology

publication icon
Blake M (2020) Quantum Circuits with Classically Simulable Operator Scrambling. in Physical review letters

publication icon
De Silva N (2021) Efficient quantum gate teleportation in higher dimensions in Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences

publication icon
Doriguello J (2021) Quantum Random Access Codes for Boolean Functions in Quantum

publication icon
Hebenstreit M (2020) Computational power of matchgates with supplementary resources in Physical Review A

publication icon
Mann R (2021) Efficient algorithms for approximating quantum partition functions in Journal of Mathematical Physics

 
Description This project was part of a collaborative network of groups across Europe working on algorithms for quantum computers. Quantum computers use quantum mechanics to outperform standard computers for certain tasks; however, designing quantum algorithms can be very challenging. In this project, we developed quantum algorithms for a variety of tasks, including numerical optimisation; simulation of quantum physics; machine learning; solving systems of equations; solving hard constraint satisfaction problems; and more. We also developed protocols for verifying quantum computers and proved limitations on their performance.
Exploitation Route The quantum algorithms developed in this project can be built on by other theorists working in the field of quantum computing; they can also be applied by practitioners to their problems. Small-scale versions of the algorithms could be implemented on quantum hardware.
Sectors Chemicals,Digital/Communication/Information Technologies (including Software),Energy,Financial Services, and Management Consultancy

 
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  
 
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 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.