QIOA: Quantum Inspired Optimisation Algorithm

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/304417
Download file(s):
File Description SizeFormat 
QIOA Quantum Inspired Optimisation Algorithm.pdf9.86 MBAdobe PDFView/Open
Bibliographical item details
Type: Examensarbete för masterexamen
Title: QIOA: Quantum Inspired Optimisation Algorithm
Authors: Sreedhar, Rishi
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.
Keywords: Tensor Networks, QAOA, Quantum-inspired algorithms, Optimisation problems
Issue Date: 2021
Publisher: Chalmers tekniska högskola / Institutionen för mikroteknologi och nanovetenskap (MC2)
URI: https://hdl.handle.net/20.500.12380/304417
Collection:Examensarbeten för masterexamen // Master Theses

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.