A cross-platform study of near-term quantum optimisation algorithms on the graphene defect problem

Abstract

Quantum computers show potential for achieving computational advantage over classical computers, with many candidate applications in combinatorial optimisation. We present a focussed, application-level hardware case study of near-term quantum optimisation algorithms applied to a dense quadratic unconstrained binary optimisation (QUBO) materials science problem. To solve this problem, we implement two methods, the variational quantum eigensolver and quantum annealing (QA), on commercially-available gate-based and QA devices that are accessible via Quantum-Computing-as-a-Service (QCaaS) models. To analyse the performance of these algorithms on our chosen problem, we use a toolbox of relevant metrics and compare performance against three classical algorithms. We employ quantum methods to solve our fully-connected QUBO of up to 72 variables, and find that algorithm performance beyond this is restricted by device connectivity, noise and classical computation time overheads. The classical method—simulated annealing—demonstrates the best performance, exhibiting polynomial scaling on the tested problem sizes.