Near-term quantum computing for solving hard industrial optimisation problems

Optimisation and constraint satisfaction problems are ubiquitous in industry, ranging from straightforward tasks such as arranging a timetable to exceptionally challenging ones such as laying out a telecommunications network or a high-performance integrated circuit. Problems like this are associated with the need to search over exponentially many potential solutions to find the best possible solution. Finding better solutions to optimisation problems could enable outcomes as diverse as reducing shipping costs for package deliveries and increasing the capacity of cellular networks. Yet these problems remain exceptionally challenging for standard computers, despite many years of effort from theorists and practitioners.

It has been known since the 1990s that quantum computers could solve optimisation problems significantly more quickly than standard computers. For example, Grover's famous quantum search algorithm can solve optimisation problems with a runtime that scales like the square root of the runtime of classical unstructured search. However, this approach and others for solving optimisation problems are suitable only for long-term, fault-tolerant quantum computing, raising the question of whether quantum computers can be applied to optimisation problems in the near future, enabling them to unlock the associated value.

In this project we will determine the potential for near-term gate-model quantum computing to solve optimisation problems. Project partner BT will identify problems, in particular in the domain of telecoms network optimisation, that are particularly suited to being solved by quantum computers. Project partner Phasecraft will design and implement quantum algorithms for these and related problems, which will be executed and evaluated on cutting-edge quantum hardware developed by project partner Rigetti. Commercial feasibility of the results of the project will be evaluated by comparing against leading classical approaches for solving optimisation problems.

Our work will build on the results of a previous InnovateUK funded feasibility study, which explored the potential for fault-tolerant quantum computers to solve optimisation problems relevant to telecom networks in the long term, but did not implement near-term algorithms on real hardware.

We will hold an innovation workshop targeted at leading organisations for whom optimisation problems are relevant to their businesses, to determine which problems are the most promising to be addressed by quantum computing and to present the results of the project. We expect that the project will deliver a quantum solution for solving optimisation problems, demonstrated on real quantum hardware, as well as a clear roadmap for applicability to real-world problems.