Quantum algorithms can be used to solve many combinatorial optimisation problems that have real-world applications, like supply chain optimisation, job scheduling, artificial intelligence, machine learning, data mining and drug designing, to name a few. These problems are NP-hard—there are no classical algorithms capable of solving all instances of the problem in polynomial time.

Quantum algorithms have attracted interests from industry like DHL, BMW, Volkswagen, Transport NSW and government agencies. Even a 1% improvement over existing solutions, when applied to a large-scale problem, would translate to significant savings in cumulative passenger travelling times and reduced greenhouse emission.

We developed a quantum-inspired classical algorithm that outperforms the state-of-the-art Goemans-Williamson algorithm for a family of MaxCut problems on significant instances [1]. This algorithm leads to efficient classical algorithms that can already be adopted to solve large scale problems. This result is unexpected and counter-intuitive in that it shows a quantum algorithm that initially cannot be simulated classically converging to a classical result.

We are exploring, developing and testing new ideas for quantum and classical algorithms for different combinatorial optimisation problems. These involve formulating the optimisation problem and constraints to a physical model that can then be solved on a quantum computer.

[1] https://arxiv.org/abs/2302.04479