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.
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.
People |
ORCID iD |
Ashley Montanaro (Principal Investigator) |
Publications
Campbell E
(2019)
Applying quantum algorithms to constraint satisfaction problems
in Quantum
Montanaro A
(2020)
Quantum speedup of branch-and-bound algorithms
in Physical Review Research
Montanaro A
(2019)
Quantum speedup of branch-and-bound algorithms
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. A subsequent project has started in 2022 to build on the results of this project by investigating near-term quantum algorithms for optimisation problems, led by quantum software startup Phasecraft and working with BT. |
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 | (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 |
Description | Phasecraft develops quantum software, with applications in modelling and simulations, allowing scientists to predict the outcomes of chemical reactions. |
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. |
Website | http://www.phasecraft.io |