Primerjava optimiranja v gamsu ter na kvantnem računalniku : magistrsko delo

Zimšek, Matija

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Primerjava optimiranja v gamsu ter na kvantnem računalniku : magistrsko delo
Authors:	ID Zimšek, Matija (Author) ID Nemet, Andreja (Mentor) More about this mentor... ID Bogataj, Miloš (Comentor)
Files:	MAG_Zimsek_Matija_2023.pdf (2,76 MB) MD5: C910B67E4B89EC689863CD09B8B8438C
Language:	Slovenian
Work type:	Master's thesis/paper
Typology:	2.09 - Master's Thesis
Organization:	FKKT - Faculty of Chemistry and Chemical Engineering
Abstract:	Za razliko od klasičnih računalnikov, kvantni računalniki (KR) izkoriščajo kvantno-mehanske pojave za izvajanje logičnih operacij. Osnovna enota v KR se imenuje kvantni bit ali kubit. Kvantno stanje kubitov lahko predstavimo kot superpozicijo njihovih osnovnih stanj, kar jih razlikuje od klasičnih bitov, ki so lahko v enem od dveh ločenih stanj. Čeprav je pri kubitih možnih neskončno kvantnih stanj, se po meritvi sesedejo v eno od svojih osnovnih stanj. Dodatna elegantna lastnost kubitov je njihova sposobnost, da med seboj tvorijo prepletena stanja, kar omogoča oblikovanje soodvisnosti med posameznimi naključnimi vedenji dveh kubitov. Tako lahko KR izkoriščajo lastnosti superpozicije in prepletenosti za izvajanje izračunov. Tekom razvoja KR se je preizkusil širok spekter področij, kjer bi lahko bili uporabljeni, ampak hitro je postalo jasno da se lahko računska prednost KR izrazi le pri nekaterih nalogah in razredih problemov. Eden izmed njih so podrazred kombinatoričnih optimizacijskih problemov imenovani QUBO problemi. Prednost njih je ta, da jih je možno rešiti direktno na KR, ki uporabljajo efekt imenovan quantum annealing (QA). QA je pristop k reševanju optimizacijskih problemov, ki omogoča izogibanje lokalnemu minimumu. Specifičen tip KR s katerimi je možno uporabljati efekt QA razvija podjetje D-Wave systems Inc, ki ponujajo nabor orodij preko vmesnika Python imenovan Ocean software development kit. V tem delu smo preverili zmožnost KR D-Wave pri reševanju dveh različnih optimizacijskih problemov, problem pakiranja in problem določitve lokacije električnih polninic. Dobljene rezultate smo primerjali z rešitvami, pridobljenimi v programskem okolju GAMS. Dodatno smo ocenili prednosti in slabosti optimiranja na KR. Prav tako smo pregledali dosedanje strokovno delo na področju QA in KR D-Wave. Primerjava rezultatov na primeru pakiranja, je pokazala minimalne razlike med programoma, saj smo s pomočjo programa D-Wave pridobili rezultate, ki so odstopale manj kot 1% tudi pri večji množici vhodnih podatkov v primerjavi z rezultati, ki smo jih dosegli v okolju GAMS. Z drugim analiziranim primerom, problemom postavitve polnilnih postaj, pa je bilo primerjavo programov možno izvesti v skrajnosti. Zgodnji rezultati so pokazali, da je D-Wave sposoben najti solidne rešitve v bistveno krajšem času kot GAMS. Nadaljno raziskovanje z več različnimi vhodnimi podatki pa je povzročilo dvom v smiselnost razulatov, ki jih ponudi QA D-Wave. Zaključili smo lahko da D-Wave predstavlja koristno orodje, v kolikor je uporabljeno v razumnih mejah in so rezultati logično interpretirani koliko so uporabni in smiselni za nadaljno uporabo.
Keywords:	Kvantni računalnik, optimizacija, quantum annealing, GAMS, problem pakiranja, problem postavitve polnilnih postaj
Place of publishing:	Maribor
Place of performance:	Maribor
Publisher:	[M. Zimšek]
Year of publishing:	2023
Number of pages:	1 spletni vir (1 datoteka PDF (IX, 63 f.))
PID:	20.500.12556/DKUM-84631
UDC:	[530.145:004]:66.011(043.2)
COBISS.SI-ID:	163407875
Publication date in DKUM:	18.07.2023
Views:	645
Downloads:	76
Metadata:
Categories:	KTFMB - FKKT
:	Copy citation

Average score:	(0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Licences

License:	CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Link:	http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:	The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.
Licensing start date:	30.06.2023

Secondary language

Language:	English
Title:	Comparison of optimisation in gams and on a quantum computer
Abstract:	Unlike classical computers, QC exploits quantum-mechanical phenomena to perform logical operations. The basic unit in QC is called a quantum bit or qubit. The quantum state of qubits can be represented as a superposition of their ground states, which distinguishes them from classical bits, which can be in one of two separate states. Although there are infinite possible quantum states for qubits, they collapse into one of their ground states after measurement. An additional elegant feature of qubits is their ability to form entangled states between themselves, which makes it possible to form correlations between the individual random behaviours of two qubits. Thus, QC can exploit the properties of superposition and entanglement to perform computations. During the development of QC, a wide range of areas where they could be used were tested, but it quickly became clear that the computational advantage of QC could only be expressed in certain tasks and classes of problems. One of these is a subclass of combinatorial optimisation problems called QUBO problems. They have the advantage that they can be solved directly on QC using an effect called QA. QA is an approach to solving optimisation problems that allows the local minimum to be avoided. A specific type of QC with which the QA effect can be used is being developed by D-Wave systems Inc, who offer a set of tools via a Python interface called the Ocean software development kit. In this work, we have verified the capability of QC D-Wave in solving two different optimization problems, the packing problem and the electric charge location problem. The results obtained were compared with the solutions obtained in the GAMS software environment. In addition, we evaluated the advantages and disadvantages of QC optimisation. We also reviewed the previous work in the field of QA and QC D-Wave. Comparison of the results on the packaging example showed minimal differences between the two programs, as we obtained results with D-Wave that deviated less than 1% even with a larger set of input data compared to the results obtained in the GAMS environment. However, with the second case analysed, the charging station layout problem, it was possible to take the comparison to extremes. Early results have shown that D-Wave is able to find solid solutions in significantly less time than GAMS. However, further exploration with several different inputs has led to questioning the reasonableness of the debugging offered by D-Wave QA. We can conclude that D-Wave is a useful tool as long as it is used within reasonable limits and the results are logically interpreted as far as they are useful and meaningful for further use.
Keywords:	Quantum computer, optimization, quantum annealing, GAMS, knapsack problem, charging stations layout problem

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back