Quantum algorithms for optimised planning/scheduling applications

Lead Research Organisation: University of Bristol
Department Name: Mathematics

Abstract

This project will investigate the technical and business feasibility of exploiting quantum algorithms for optimised planning tasks, in close collaboration with key industry and academic partners. It aims to prove the technical feasibility of enhancing existing artificial intelligence (AI) planning techniques with quantum algorithms, either as fully quantum or hybrid solutions, combining both quantum and conventional computing methods. We will perform experiments to establish benchmarks for enhancing AI planning techniques with early quantum annealing algorithms, and then determine how they might be further enhanced with other universal quantum computing or 'circuit-model' approaches. In addition, this project will perform a market assessment for quantum-enhanced optimised planning solutions and determine the business feasibility of commercialising them for several markets, including telecoms network optimisation, distribution logistics and operational planning. This will help to stimulate wider interest with potential end-users and quantum computing vendors to develop optimisation tools for specific markets, and deliver potential major productivity gains for transport, logistics, energy and finance.

Planned Impact

Economic: In addition to economic benefits to our industry partner BT in telecom optimisation, the outputs of this feasibility study will stimulate wider interest in quantum-enhanced tools not only with innovation workshop participants, but also with other potential industry end users, who will receive our reports. It will also encourage other quantum computing vendors (including large technology companies and academic spin-offs) to develop optimisation tools for specific markets, and others in the supply chain to integrate early quantum annealers within hybrid solutions, as is already happening in the finance sector. Such optimisation products could generate large productivity gains for transport, logistics, energy, and retail. It could also disrupt key markets where UK already has strong positions, such as finance, aerospace and pharmaceuticals, and enable growth in new emerging markets that could also benefit from quantum-enhanced optimisation (e.g. blockchain).

Social: The social impact of wider introduction of optimisation tools could lead to better and earlier recognition of fraud/criminal activities, especially organised crime and deterence for specific classes of crime (e.g. cyber/financial fraud) which have been increasing greatly over the past few years, rising from $400Bn (2015) to $2trillion (2019). Optimisation tools could lead to better government social policy, financial regulation and impact of legislation on wider society. The World Development Bank Report (1997) determined the projected benefit on GDP of better regulation/de-regulation on developed countries ranged from 0.3% (US/Germany) to 18.7% (Japan), with the EU (3-7%).

Environmental: Better optimisation could lead to less traffic/pollution on transport networks, less resources used (materials/fuel) and less destructive failures due to predictive analytics. Not every vehicle would require a quantum processor, since optimisation solutions would most likley be accessed from cloud-based quantum information services.

Regional/national/global: Most of the potential impacts of quantum-enhanced optimisation tools described above have been highlighted at the regional/national/global level, including optimisation for telecoms/transport/logistics/energy grid networks, manufacturing/predictive fault management, regulatory compliance and complex plan recognition for cyber threats, financial fraud and other criminal behaviours.

Publications

10 25 50

publication icon
Montanaro A (2020) Quantum speedup of branch-and-bound algorithms in Physical Review Research

 
Description This 12-month feasibility study performed experiments with quantum annealing systems on a variety of optimisation problems, together with a comparative analysis with universal (gate-model) quantum computing (QC) approaches. It held a 'market-focussed' innovation workshop with 50+ people from key industry sectors (potential end-users), as well as quantum computing experts from academia, industry and other quantum stakeholders.

The key results of the component on gate-model quantum computing (the main part of the project to which I contributed) were a detailed analysis of algorithmic complexity showing that quantum computers could potentially provide a large speedup over a standard classical desktop computer for solving optimisation problems relevant to practical applications, but that the hardware requirements to achieve this are currently daunting.
Exploitation Route We gave the first detailed analysis of the potential speedup that could be obtained by using quantum algorithms to solve constraint satisfaction problems, and the corresponding hardware parameters required. This will inform end-users; will be a foundation for future studies by others analysing other problems and improving our results; and will provide motivation to improve quantum fault-tolerance techniques.
Sectors Aerospace, Defence and Marine,Digital/Communication/Information Technologies (including Software),Electronics,Energy,Financial Services, and Management Consultancy,Manufacturing, including Industrial Biotechology

URL https://admin.ktn-uk.co.uk/app/uploads/2018/12/D008-Final-report-QCAPS-project-v1.0.pdf
 
Description Towards the end of the project, we held a 'market-focussed' innovation workshop in London. It involved more than 50 people from key industry sectors (potential end-users), as well as quantum computing experts from academia/industry and other quantum stakeholders/fund-holders. The purpose of this innovation workshop was to provide an update on current experiments with quantum annealing systems and future applications of universal circuit-model approaches. It also provided case studies on the applications of quantum annealing techniques to specific problems in three business sectors: telecoms network optimisation (BT), traffic-flow optimisation (VW) and distribution logistics (Ocado). In addition, the workshop comprised brainstorming sessions to explore other applications of hybrid quantum-classical approaches for three key market sectors, including market-focussed aspects (e.g. market size, timelines, enablers and barriers). The workshop outputs, together with further business analysis have informed a 'road-mapping' activity sponsored by InnovateUK and supported by the UK Quantum Technology Programme.
First Year Of Impact 2018
Sector Aerospace, Defence and Marine,Digital/Communication/Information Technologies (including Software),Electronics,Energy,Manufacturing, including Industrial Biotechology
Impact Types Economic

 
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 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 with BT 
Organisation BT Group
Country United Kingdom 
Sector Private 
PI Contribution We applied our expertise in the development of quantum algorithms to network optimisation problems of interest to BT.
Collaborator Contribution BT used their subject matter expertise on problems relating to network optimisation to provide problems of practical interest that could be good candidates for finding more efficient solutions using a quantum computer.
Impact A final report was prepared, hosted by InnovateUK: https://admin.ktn-uk.co.uk/app/uploads/2018/12/D008-Final-report-QCAPS-project-v1.0.pdf Following this partnership, BT has decided to be a partner on subsequent grant applications to EPSRC, making very substantial in-kind contributions. The project was multi-disciplinary, including computer scientists, mathematicians and physicists.
Start Year 2017
 
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.