Quantum algorithms for optimised planning/scheduling applications (Feasibility Study)
Lead Research Organisation:
University College London
Department Name: London Centre for Nanotechnology
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
The market for optimised planning/scheduling is currently focussed on modest complexity tasks, such as gate scheduling at airports/train stations, bank/insurance fraud detection for individual crimes, and route planning for individual vehicles or small fleets (trucks). There are 6.2M commercial fleet software units currently active in Europe, with consumer route planning products (e.g. TomTom) 10-20 times greater (both growing at 15% pa). The existing global market for transport data analytics has grown to £8Bn in 2015 (Transport Systems Capault) and to £16Bn by 2020 for wider transport management systems markets (Market&Markets).
For more complex optimisation tasks (e.g. integrated manufacturing and distribition logistics planning across market sectors and traffic optimisation across regional/global networks, the markets for optimisation products are still emerging, awaiting processing power, beyond conventional tools. Gartner estimated the size of global supply chain management (SCM) software market at $8.3Bn (2013) and projected to grow to $13.4Bn (2017). With hybrid quantum optimisation products, these markets could become more integrated, less focussed on single sectors and address more complex planning/scheduling tasks. Lloyds of London estimate global losses due to cyber crime at $400Bn pa (2015) and projected to reach $2trillion (2019). Current analytic tools target the detection of individual crimes/fraud, rather than the recognition of market-wide financial crises/abuses (e.g. sub-prime mortgage collapse and LIBOR manipulation), and major cyber threats against critical national infrastructure. Cybersecurity Ventures predicts hot growth in services for threat intelligence (10+% pa), and cloud security (50% pa), with the cloud security market to grow to $8.7Bn by 2019. Rather than addressing optimisation problems within specific industries with discrete products optimising individual performance, this project will explore the market potential for services enabled by hybrid quantum computing products, potentially as cloud-based services, that will help to optimise traffic flows/product deliveries (every second) across vast networks globally. Such tools would enable predictive analytics to diagnose faults 'before they become problems' and target organised crime rings, as well individual criminals. Our industry partner (BT) will determine how best to expand the market for telecoms network optimisation products, and other solutions for optimised planning/scheduling tools within the telecoms market sector.
We plan to invite key UK organisations to our innovation workshops from various market sectors: oil/gas (BP/Shell); distribution logistics (Amazon, Ocado); finance (HSBC, AMEX, HMRC); law enforcement (Met Police, National Crime Agency); and other government (National Cyber Security Centre). They will help us to determine which parts of their markets to emphasise and understand how best to develop channels into and across them.
For more complex optimisation tasks (e.g. integrated manufacturing and distribition logistics planning across market sectors and traffic optimisation across regional/global networks, the markets for optimisation products are still emerging, awaiting processing power, beyond conventional tools. Gartner estimated the size of global supply chain management (SCM) software market at $8.3Bn (2013) and projected to grow to $13.4Bn (2017). With hybrid quantum optimisation products, these markets could become more integrated, less focussed on single sectors and address more complex planning/scheduling tasks. Lloyds of London estimate global losses due to cyber crime at $400Bn pa (2015) and projected to reach $2trillion (2019). Current analytic tools target the detection of individual crimes/fraud, rather than the recognition of market-wide financial crises/abuses (e.g. sub-prime mortgage collapse and LIBOR manipulation), and major cyber threats against critical national infrastructure. Cybersecurity Ventures predicts hot growth in services for threat intelligence (10+% pa), and cloud security (50% pa), with the cloud security market to grow to $8.7Bn by 2019. Rather than addressing optimisation problems within specific industries with discrete products optimising individual performance, this project will explore the market potential for services enabled by hybrid quantum computing products, potentially as cloud-based services, that will help to optimise traffic flows/product deliveries (every second) across vast networks globally. Such tools would enable predictive analytics to diagnose faults 'before they become problems' and target organised crime rings, as well individual criminals. Our industry partner (BT) will determine how best to expand the market for telecoms network optimisation products, and other solutions for optimised planning/scheduling tools within the telecoms market sector.
We plan to invite key UK organisations to our innovation workshops from various market sectors: oil/gas (BP/Shell); distribution logistics (Amazon, Ocado); finance (HSBC, AMEX, HMRC); law enforcement (Met Police, National Crime Agency); and other government (National Cyber Security Centre). They will help us to determine which parts of their markets to emphasise and understand how best to develop channels into and across them.
Publications
Fang Y
(2020)
Minimizing minor embedding energy: an application in quantum annealing
in Quantum Information Processing
Description | Quantum algorithms (including quantum annealing) may in the future have a transformational impact on planning and scheduling applications in industry. Hardware resources are currently not sufficiently mature however. |
Exploitation Route | Development of quantum algorithms in specific business sectors |
Sectors | Aerospace, Defence and Marine,Digital/Communication/Information Technologies (including Software),Electronics,Energy,Environment,Financial Services, and Management Consultancy,Healthcare,Manufacturing, including Industrial Biotechology,Pharmaceuticals and Medical Biotechnology,Retail,Transport |
Description | Report on quantum computation for business applications |
First Year Of Impact | 2018 |
Sector | Aerospace, Defence and Marine,Digital/Communication/Information Technologies (including Software),Electronics,Energy,Healthcare,Manufacturing, including Industrial Biotechology,Pharmaceuticals and Medical Biotechnology,Transport |
Impact Types | Economic |
Description | International Network on Quantum Annealing (INQA) |
Amount | £321,864 (GBP) |
Funding ID | EP/W027003/1 |
Organisation | Engineering and Physical Sciences Research Council (EPSRC) |
Sector | Public |
Country | United Kingdom |
Start | 02/2022 |
End | 02/2025 |
Description | Quantum Annealing for Telecoms Optimisation |
Amount | £36,000 (GBP) |
Funding ID | 2148419 |
Organisation | Engineering and Physical Sciences Research Council (EPSRC) |
Sector | Public |
Country | United Kingdom |
Start | 01/2019 |
End | 07/2022 |
Description | Quantum Enhanced and Verified Exascale Computing - QEVEC |
Amount | £1,007,642 (GBP) |
Funding ID | EP/W00772X/2 |
Organisation | Engineering and Physical Sciences Research Council (EPSRC) |
Sector | Public |
Country | United Kingdom |
Start | 11/2021 |
End | 07/2024 |
Description | BT |
Organisation | BT Group |
Department | BT Research |
Country | United Kingdom |
Sector | Private |
PI Contribution | Research into telecoms network optimisation using quantum annealing |
Collaborator Contribution | Specification of telecoms network problems |
Impact | Report on quantum computation business applications |
Start Year | 2017 |