Quantum annealing (QA) is an optimization process in quantum computing similar to the probabilistic metaheuristic simulated annealing (SA). The QA process involves encoding an optimization problem into an energy landscape, which it then traverses in search for the point of minimal energy representing the global optimal state. In this thesis two different implementations of QA are examined, one run on a binary quadratic model (BQM) and one on a discrete quadratic model (DQM). These are then compared to their traditional counterpart: SA, in terms of performance and accuracy when solving the graph coloring problem (GCP). Regarding performance, the results illustrate how SA outperforms both QA implementations. However, it is apparent that these slower execution times are mostly due to various overhead costs that appear because of limited hardware. When only looking at the quantum annealing part of the process, it is about a hundred times faster than the SA process. When it comes to accuracy, both the DQM-implementation of QA and SA provided results of high quality, whereas the BQM-implementation performed notably worse, both by often not finding the optimal values and by sometimes returning invalid results. / Quantum annealing (QA) är en kvantbaserad optimeringsprocess som liknar den probabilistiska metaheuristiken simulated annealing (SA). QA går ut på att konvertera ett optimeringsproblem till ett energilandskap, som sedan navigeras för att hitta punkten med lägst energi, vilket då motsvarar den optimala lösningen på problemet. I denna uppsats undersöks två olika implementationer av QA: en som använder en binary quadratic model (BQM) och en som använder en discrete quadratic model (DQM). Dessa två implementationerna jämförs med deras traditionella motsvarighet: SA, utifrån både prestanda och korrekthet vid lösning av graffärgningsproblemet (GCP). När det gäller prestanda visar resultaten att SA är snabbare än båda QA implementationerna. Samtidigt är det tydligt att denna prestandaskillnad framförallt beror på diverse förberedelser innan exkueringen startar på kvantdatorn, vilka är krävande på grund av olika hårdvarubegränsningar. Om man endast betraktar kvantprocesserna visar vår studie att QA implementationerna är ungefär hundra gånger snabbare än SA. Gällande korrekthet gav både DQM-implementationen av QA och SA resultat av hög kvalitet medan BQM-implementationen presterade betydligt sämre. Den gjorde detta dels genom att inte skapa optimala resultat och genom att returnera otillåtna lösningar.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-336617 |
| Date | January 2023 |
| Creators | Odelius, Nora, Reinholdsson, Isak |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2023:328 |
Page generated in 0.0023 seconds