20.500.12556/RUL-159791 Reševanje problema maksimalnega prereza s kvantnim računalnikom delo diplomskega seminarja Solving maximum cut problem with quantum computer Tako kot so bili klasični računalniki v začetku razvoja velike in okorne naprave, v katerih je lahko prišlo do napake v računanju, so nekako v tej fazi razvoja sedaj kvantni računalniki. V diplomskem delu bom predstavil tri vodilna podjetja v kvantnem računalništvu, D-Wave, Google in IBM. Ti kvantni računalniki niso namenjeni za splošno uporabo, specializirani so za tri stvari: reševanje optimizacijskih problemov, simulacijo molekul in generiranje diskretnih porazdelitev. V diplomskem delu se bom posvetil reševanju optimizacijskega problema s kvantnim računalnikom, ki mu rečemo problem maksimalnega prereza. Ta problem spada pod razred NP-polnih problemov in je v primerih večjih problemov s klasičnim računalnikom praktično nerešljiv. Tu nam pride prav kvantna mehanika, ki pravi, da se kubit lahko nahaja v več stanjih naenkrat, to lastnost lahko izkoristimo za računanje optimizacijskih problemov, ki jih znamo zapisati v kvantni računalnik. Če znamo problem zapisati v obliki energije Hamiltonove funkcije, potem ga lahko tudi zapišemo v kvantni računalnik in nam ta zna pridelati smiselno rešitev. Eden od optimizacijskih problemov, ki jih znamo zapisati z energijo Hamiltonove funkcije, je problem kvadratične binarne optimizacije brez omejitev, tega pa je mogoče prikazati kot ekvivalenten problem maksimalnega prereza, kar nam da nov kvantni pristop k reševanju problema maksimalnega prereza. V diplomskem delu bom pokazal, da lahko vsak problem maksimalnega prereza zapišemo kot problem kvadratične binarne optimizacije brez omejitev, nato bom s prevedbo problema maksimalnega prereza na problem kvadratične binarne optimizacije brez omejitev poiskal dobre rešitve za problem maksimalnega prereza za večje grafe ($250 \le n$) s pomočjo kvantnega računalnika D-Wave in te rešitve primerjal z optimalnimi rešitvami. Potem bom še pogledal učinkovitost reševanja problema maksimalnega prereza z uporabo kvantnih računalnikov proizvajalcev Google in IBM, ki ne dopuščajo vnosov tako velikih problemov kot D-Wave, in naredil primerjavo prerezov med vsemi računalniki z namenom, da vidim, kateri je najbolj primeren za iskanje maksimalnega prereza. Just as were classical computers in the beginning of development large and cumbersome devices, in which errors in calculation could occur, somehow in this phase of development are now quantum computers. In this thesis, I will present three leading companies in quantum computing, which are D-Wave, Google and IBM. These quantum computers are not intended for general use, they specialize in three things, solving optimization problems, simulating molecules and generating discrete distributions. In the thesis, I will focus on solving optimization problem called maximum cut problem with a quantum computer. This problem belongs to the class of NP-complete problems and is practically unsolvable for larger instances with a classical computer. Here comes in handy quantum mechanics, which says that a qubit can be in multiple states at once, we can exploit this property for computing optimization problems that we can express in a quantum computer. If we can express the problem in the form of the energy of the Hamiltonian function, then we can also write it in a quantum computer, and it can provides us with a meaningful solution. One of the optimization problems that we can express with the energy of the Hamiltonian function is the problem of quadratic unconstrained binary optimization, and this can be shown as an equivalent problem of the maximum cut problem. In the thesis, I will show that we can express any maximum cut problem as an quadratic unconstrained binary optimization problem, then, by translating the maximum cut problem into an quadratic unconstrained binary optimization problem, I will try to solve the maximum cut problem for larger instances of graphs ($250 \le n$) with the help of D-Wave's quantum computer. Then, I will also look at the efficiency of solving maximum cut problem of the other two quantum computers (Google and IBM), which do not allow inputs as large as D-Wave, and make a comparison of cuts between all computers with the aim of seeing which one is most suitable for finding the maximum cut. Kvantna premoč binarni kvadratični model kvadratična binarna optimizacija brez omejitev maksimalni prerez D-Wave Quantum supremacy binary quadratic model quadratic unconstrained binary optimization maximum cut D-Wave true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2024-07-25 08:15:03 2024-07-25 08:15:13 2024-07-26 08:56:50 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.8 140161 202870275 12161.pdf 12161.pdf 1 6F98E41DAA894239178C72055A5417ED 584248d9890ab0e37a453388f3ed749a564c63eab9c6efa481df43867be3c55c 296542d1-4a4d-11ef-8f74-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=187994 Fakulteta za matematiko in fiziko 0 0 0