Determining the viability of quantum algorithms run on near term faulty and long term fault tolerant quantum computers to provide a speed up over classical algorithms for the quadratic knapsack problem (QKP) with applications to defence acquisition.

Spherical shape glowing blue with code on dark background

Source: Adobe Stock

‘Defence Acquisition Optimisation Using Quantum Algorithms’ with Defence Innovation Network (DIN)

Aim and background

Determining the viability of quantum algorithms run on near term faulty and long term fault tolerant quantum computers to provide a speed up over classical algorithms for the quadratic knapsack problem (QKP) with applications to defence acquisition.

The aim is to deliver concrete estimates of both the running time and computational resources required for both a Noisy Intermediate-Scale Quantum (NISQ) computer and fault-tolerant quantum computer to solve the QKP using heuristic methods. By comparing these concrete estimates to the capabilities of classical computers, researchers will forecast if/when a quantum computer will outperform a classical computer for the QKP.

Research project and expected outcomes

This research project draws upon QSI’s world leading research in quantum optimisation algorithms. Fundamentally new quantum algorithms will be developed to assess the viability of quantum computing for solving the QKP, using four main approaches: 

  1. Mapping the problem to a Hamiltonian to be implemented on a NISQ annealer.
  2. Using a quantum walk implementation of Markov-chain Monte Carlo.
  3. Applying a quantum algorithm for the branch-and-bound approach to QKP.
  4. Heuristics based on a semidefinite programming (SDP) relaxation of the problem.

The developed algorithm will have potential application to several optimisation problems, such as the distribution of sensors and radars and communication problems. 

QSI Investigators 

Dates

October 2021 – Current 

Focused research outputs