An investigation of IBM Quantum Computing deviceperformance on Combinatorial Optimisation Problems

Maxine T. Khumalo, Hazel A. Chieza, Krupa Prag, Matthew Woolway

Published 2021-07-08Version 1

The exponential increase in CPU time taken to deterministically solve NP-Hard Combinatorial Optimisation Problems (COP), as the problem size scales, has resulted in a search for non-deterministic optimisation solution techniques to obtain solutions to COP efficiently. This paper juxtaposes classical and quantum optimisation algorithms' performance to solve two common COP, the Travelling Salesman Problem (TSP) and Quadratic Assignment Problem (QAP). The two classical optimisation techniques applied are Branch and Bound (BNB) and Simulated Annealing (SA), and the two quantum optimisation methods used are the Variational Quantum Eigensolver (VQE) algorithm and Quantum Approximate Optimisation Algorithm (QAOA). These algorithms are respectively executed on classical and IBM's suite of Noisy Intermediate-Scale Quantum (NISQ) computers. Our experimental results resemble and extend on previously reported results in the literature. Extensions include critically analysing, comparing and commenting on the performance of quantum optimisation computing techniques to classical techniques, with respect to computational time and additional metrics used to measure solution quality. Furthermore, a comparison of the impact of a new set of basis gates on the quantum optimisation techniques was investigated; the results did not reflect any consistent impact on results. The VQE algorithm and QAOA executed on state of the art IBM quantum devices are outperformed by classical optimisation techniques, highlighting the shortcomings of NISQ devices.