QIOA: Quantum Inspired Optimisation Algorithm

Visa enkel post
dc.contributor.authorSreedhar, Rishi
dc.contributor.departmentChalmers tekniska högskola / Institutionen för mikroteknologi och nanovetenskap (MC2)sv
dc.contributor.examinerJohansson, Göran
dc.contributor.examinerBauch, Thilo
dc.contributor.supervisorSorée, Bart
dc.contributor.supervisorJosefsson Ask, Andreas
dc.date.accessioned2021-12-23T05:20:58Z
dc.date.available2021-12-23T05:20:58Z
dc.date.issued2021sv
dc.date.submitted2020
dc.description.abstractThe 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.sv
dc.identifier.coursecodeMCCX04sv
dc.identifier.urihttps://hdl.handle.net/20.500.12380/304417
dc.language.isoengsv
dc.setspec.uppsokPhysicsChemistryMaths
dc.subjectTensor Networks, QAOA, Quantum-inspired algorithms, Optimisation problemssv
dc.titleQIOA: Quantum Inspired Optimisation Algorithmsv
dc.type.degreeExamensarbete för masterexamensv
dc.type.uppsokH
Ladda ner
Original bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
QIOA Quantum Inspired Optimisation Algorithm.pdf
Storlek:
9.63 MB
Format:
Adobe Portable Document Format
Beskrivning:
Ladda ner
License bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
license.txt
Storlek:
1.51 KB
Format:
Item-specific license agreed upon to submission
Beskrivning:
Ladda ner
Samling
Examensarbeten för masterexamen