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

Zimšek, Matija

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	Primerjava optimiranja v gamsu ter na kvantnem računalniku : magistrsko delo
Avtorji:	ID Zimšek, Matija (Avtor) ID Nemet, Andreja (Mentor) Več o mentorju... ID Bogataj, Miloš (Komentor)
Datoteke:	MAG_Zimsek_Matija_2023.pdf (2,76 MB) MD5: C910B67E4B89EC689863CD09B8B8438C
Jezik:	Slovenski jezik
Vrsta gradiva:	Magistrsko delo/naloga
Tipologija:	2.09 - Magistrsko delo
Organizacija:	FKKT - Fakulteta za kemijo in kemijsko tehnologijo
Opis:	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.
Ključne besede:	Kvantni računalnik, optimizacija, quantum annealing, GAMS, problem pakiranja, problem postavitve polnilnih postaj
Kraj izida:	Maribor
Kraj izvedbe:	Maribor
Založnik:	[M. Zimšek]
Leto izida:	2023
Št. strani:	1 spletni vir (1 datoteka PDF (IX, 63 f.))
PID:	20.500.12556/DKUM-84631
UDK:	[530.145:004]:66.011(043.2)
COBISS.SI-ID:	163407875
Datum objave v DKUM:	18.07.2023
Število ogledov:	647
Število prenosov:	76
Metapodatki:
Področja:	KTFMB - FKKT
:	Kopiraj citat

Skupna ocena:	(0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Licence

Licenca:	CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna

Povezava:	http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
Opis:	Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.
Začetek licenciranja:	30.06.2023

Sekundarni jezik

Jezik:	Angleški jezik
Naslov:	Comparison of optimisation in gams and on a quantum computer
Opis:	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.
Ključne besede:	Quantum computer, optimization, quantum annealing, GAMS, knapsack problem, charging stations layout problem

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj