Reševanje problema maksimalnega prereza s kvantnim računalnikomStanković, Ioann (Avtor) Povh, Janez (Mentor) Kvantna premočbinarni kvadratični modelkvadratična binarna optimizacija brez omejitevmaksimalni prerezD-WaveTako 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.20242024-07-25 08:15:03Delo diplomskega seminarja/zaključno seminarsko delo/naloga159791UDK: 519.8VisID: 140161COBISS_ID: 202870275sl