20.500.12556/DKUM-84631 Primerjava optimiranja v gamsu ter na kvantnem računalniku magistrsko delo Comparison of optimisation in gams and on a quantum computer 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. 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. Kvantni računalnik optimizacija quantum annealing GAMS problem pakiranja problem postavitve polnilnih postaj Quantum computer optimization quantum annealing GAMS knapsack problem charging stations layout problem true true false [M. Zimšek] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2023-06-30 17:22:38 2023-07-18 07:39:57 2023-09-07 03:09:16 0000-00-00 00:00:00 2023 0 Maribor 0 Maribor 1 spletni vir (1 datoteka PDF (IX, 63 f.)) 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 [530.145:004]:66.011(043.2) 163407875 MAG_Zimsek_Matija_2023.pdf MAG_Zimsek_Matija_2023.pdf 1 C910B67E4B89EC689863CD09B8B8438C 54a234edcd4c45572cca92f1253d82eeb5f74713b461b670758eb769f7a6fafb 2b0b4ef0-24d4-11ee-8abb-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=168845 Fakulteta za kemijo in kemijsko tehnologijo 0 0 0