QIOA: Quantum Inspired Optimisation Algorithm

Abstract

The current era of Quantum computing has been aptly named Noisy Intermediate- Scale Quantum era, or NISQ era [1], owing to the highly promising, yet still imperfect state of available quantum hardware. The applicability of these NISQ devices available today is an area of research attracting increasing amounts of attention, as the field of quantum computing grows in popularity. Quantum-classical variational algorithms such as the Quantum Approximate Optimisation Algorithm [2], Variational Quantum Eigensolver [3], and Variational Autoencoder [4] are promising attempts in this direction, aiming to extract maximum value from NISQ devices. These algorithms aim to minimise the number of operations on the quantum processor by incorporating classical support-routine overheads. The Quantum Approximate Optimisation Algorithm, also known as QAOA [2], is one such hybrid algorithm designed to solve optimisation problems. In this thesis, we study the QAOA using the framework of tensor networks and matrix product states (MPS). We make approximations on the quantum aspects of QAOA by limiting the amount of entanglement in QAOA circuits. Then, we analyse the effect of these approximations on its performance, by applying this approximated method on multiple Max-Cut and Exact-Cover problems of different sizes. In the MPS formulation, it is the exponential increase of entanglement that makes exact simulations of highly entangled quantum circuits, such as QAOA circuits, classically infeasible. Our results suggest that it could still be possible to extract the solutions of the optimisation problems QAOA tries to solve, even from an approximated MPS-based QAOA-implementation with restricted entanglement. This added restriction in entanglement growth makes our implementation classically tractable. Hence, with this thesis, we propose a classical version of QAOA, which we are calling Quantum Inspired Optimisation Algorithm, QIOA, that is inspired by the original QAOA. We have validated the performance of QIOA on problems of small sizes, and further studies are required to better understand its limitations.