Solving the maximum cut problem using quantum circuits

No Thumbnail Available
Files
Niemikallio_Leo_2024.pdf (652.57 KB)
Journal Title
Journal ISSN
Volume Title
Sähkötekniikan korkeakoulu | Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2024-05-20
Department
Major/Subject
Automaatio ja robotiikka
Mcode
ELEC3014
Degree programme
Sähkötekniikan kandidaattiohjelma
Language
en
Pages
35
Series
Abstract
Quantum computers theoretically provide significant advantages in computational power and are evolving rapidly, however not many know how to utilize them. The goal of this bachelor's thesis is to investigate how a quantum computer can be utilized to solve the maximum cut (Max-Cut) optimization problem, and to compile the information needed to do so. The information is utilized to build an implementation, which is then evaluated mainly by simulation with some runs on a quantum computer. The core of the Max-Cut problem is how can a graph consisting of nodes and edges connecting them be divided into two such that the maximum number of edges are cut. The problem can be described by a cost-function, which can be formulated as a quadratic unconstrained binary optimization (QUBO) problem. Furthermore, this can be formulated using quantum states, which allows a quantum circuit representing a given Max-Cut instance to be built. Quantum circuits are a way of building commands for a quantum processing unit (QPU), consisting of qubits and quantum gates, and allowing for a visual representation of the commands given. An approximate solution to the Max-Cut problem can be obtained by utilizing the quantum approximate optimization algorithm (QAOA). QAOA is a hybrid algorithm as it consists of both a quantum circuit and a classical optimization algorithm. For the classical optimizer, the particle swarm optimization (PSO) was used. As a result, an implementation was obtained, which could easily be utilized to solve any other QUBO formulated problem. The implementation delivered satisfactory results for a simple Max-Cut instance. However, in the case of a more complex problem, the implementation did not perform as well although the result could be utilized to reduce the number of computation needed on a classical computer. Additionally, by comparing the final optimized parameters on a simulated and a real QPU, the observation was made that as the QAOA depth increases, the difference between the two increases as a result of the collective quantum noise. This likely means that running the QAOA on a real QPU would not yield same results as the simulated one when the problem is not a simple one.

Kvanttitietokoneet mahdollistavat teoriassa suuria etuja laskentatehossa, sekä kehittyvät nopeasti, mutta vain harva osaa hyödyntää niitä. Tämän kandidaatintyön tavoitteena on selvittää, miten kvanttitietokonetta voidaan hyödyntää maksimaalisen leikkauksen eli Max-Cut -optimointiongelman ratkaisemiseen, sekä koostaa tähän tarpeellinen taustatieto. Taustatiedon avulla rakennetaan implementaatio, jonka suorituskykyä arvioidaan pääosin simuloimalla, mutta myös todellisella kvanttitietokoneella. Max-Cut -ongelma voidaan kiteyttää kysymykseen, miten yhdistetyt pisteet voidaan jaotella kahteen ryhmään niin, että mahdollisimman monta yhteyttä katkeaa. Ongelmaa voidaan kuvata kustannusfunktiolla, joka puolestaan voidaan lausua neliöllisenä rajoittamattomana binäärioptimointiongelmana (QUBO). Tämä voidaan edelleen kirjoittaa kvanttitiloja käyttäen, minkä pohjalta voidaan rakentaa jotain tiettyä ongelmaa vastaava kvanttipiiri. Kvanttipiirit ovat tapa muodostaa ja visualisoida kvanttitietokoneelle annettavia komentoja, jotka koostuvat kubiteista ja kvanttiporteista. Max-Cut -ongelmalle saadaan likimääräinen ratkaisu hyödyntämällä likimääräistä kvanttioptimointialgoritmia (QAOA). QAOA on hybridialgoritmi, sillä se koostuu sekä kvanttipiiristä, että klassisesta optimointialgoritmista. Kvanttipiirin parametrien optimointiin käytettiin työssä hiukkasparvioptimointia (PSO). Lopputuloksena saatiin implementaatio, jota voidaan myös helposti käyttää minkä tahansa muun QUBO-ongelman ratkaisuun. Implementaatiolla saatiin yksinkertaiselle Max-Cut ongelmalle hyvä ratkaisu, mutta monimutkaisemman ongelman kanssa oikeaa tulosta ei saatu suoraan. Monimutkaisemman ongelman tapauksessa tulosta voitaisiin hyödyntää vähentämään klassisella tietokoneella laskettavien arvojen määrää. Lisäksi vertailemalla simuloituja ja todellisella kvanttitietokoneella suoritettuja loppuarvoja huomataan, että piirin kerrosmäärän kasvaessa simuloitu QAOA ei todennäköisesti vastaa oikealla kvanttitietokoneella suoritettua versiota kohinan määrästä johtuen.
Description
Supervisor
Forsman, Pekka
Thesis advisor
Galvis, Cristian
Keywords
maximum cut, quantum circuits, quantum approximate optimization algorithm, particle swarm optimization, quadratic unconstrained binary optimization
Other note
Citation
Permanent link to this item
https://urn.fi/URN:NBN:fi:aalto-202407025021
Collections
[kand] Sähkötekniikan korkeakoulu / ELEC