Reševanje problema največje neodvisne množice s kvantnimi žarilnikiKrpan, Aljaž (Avtor) Žitnik, Arjana (Mentor) Povh, Janez (Komentor) kvantni žarilnikNP-težki problemioptimizacijski problemiproblem neodvisne množiceV tem diplomskem delu raziščemo reševanje NP-težkih optimizacijskih problemov z uporabo kvantnih žarilnikov. Na začetku naprej opišemo, kako se je področje kvantnih računalnikov začelo razvijati in kje se nahaja danes. Navedemo nekaj ponudnikov kvantnih storitev za komercialno rabo, pri čemer več pozornosti posvetimo ponudniku D-Wave Systems, saj je računanje na njihovih kvantnih žarilnikih osrednja tema tega diplomskega dela. Nato sledi poglavje o procesu delovanja D-Wavovih kvantnih žarilnikov in o fizikalnih principih, na katerih sloni njihovo delovanje. Namen tega je vzpostaviti intuicijo, kako kvantni žarilnik sploh deluje. Temu sledi poglavje o pretvarjanju optimizacijskih problemov v obliko, primerno za kvantni žarilnik. S tem znanjem se bomo nato lotili problema največje neodvisne množice. Problem bomo definirali in ga pretvorili v primerno obliko za uporabo na kvantnem žarilniku. Pri tem bomo pokazali, katere druge oblike so ravno tako veljavne, vendar manj primerne. Nato bomo največjo neodvisno množico rešili na nekaj klasičnih grafih. Pokazali bomo še postopek, kako lahko dobljene rezultate obdelamo tako, da iz njih izluščimo čim boljšo rešitev. Temu sledi poglavje o zmanjševanju vhodnih podatkov za lažje računanje tega problema. To bomo počeli z razdelitvijo problema v več manjših podproblemov in z redukcijo (odstranjevanjem) vhodnih podatkov, ki ne vplivajo na končno rešitev. To nam bo omogočilo izračun problema pri nekaterih instancah problema, ki so bile prej prevelike za izračun na kvantnem žarilniku. Na koncu bomo še izpeljali algoritem, ki nam omogoča določanje (ne nujno tesne) zgornje meje, ter dodali še nekaj idej za nadaljnjo raziskovanje in izboljšave.20232023-09-08 12:00:00Diplomsko delo/naloga149706sl