Quantum algorithms for combinatorial optimisation problems

Start year: 2025

Summary: In this project we will look at quantum algorithms for combinatorial optimisation problems. This project will take place with partner KPMG to investigate quantum algorithms for optimisation problems of interest to KPMG. We will focus on NP-hard optimisation problems where the best known classical algorithms use the technique of dynamic programming, as has previously been explored in the paper "Quantum Speedups for Exponential-Time Dynamic Programming Algorithms". Classical dynamic programming algorithms are inherently sequential in nature and have proven difficult to "quantize", or turn into a quantum algorithm with a speedup. We have recently had some success in doing this (https://arxiv.org/abs/2311.16401) by developing divide and conquer algorithms for dynamic programming problems, which are inherently more amenable to quantum speedups. This project will continue to pursue this approach to find quantum speedups for combinatorial optimisation problems of practical interest.

Acknowledgement of Country

UTS acknowledges the Gadigal people of the Eora Nation, the Boorooberongal people of the Dharug Nation, the Bidiagal people and the Gamaygal people upon whose ancestral lands our university stands. We would also like to pay respect to the Elders both past and present, acknowledging them as the traditional custodians of knowledge for these lands.