Koniorczyk Mátyás [1], Naszvadi Péter [1], Pintér Miklós [2] (2023.04.18 - 07.18)

[1] Wigner Fizikai Kutatóközpont [2] Budapesti Corvinus Egyetem

Kivonat: A projekt keretében kvadratikus bináris korlát nélküli optimalizálási feladatokat (QUBO) vizsgálunk. Ezek az Ising-modellel ekvivalens nehéz számítási feladatok, és kvantum annealerek segítségével is megoldhatók. Segédváltozók bevezetésével lineáris vegyes egészértékű feladattá is átírhatók, ez a standard (Fortet) linearizáció. Kutatásunkban azt vizsgáljuk, hogy mennyiben alkalmas a Fortet linearizáció kisebb méretű feladat esetén egy valamilyen közelítő heurisztikából (pl. kvantum annealing, szimulált bifurkáció, stb.) kapott megoldás javítására, illetve az optimalitás ellenőrzésére dualitási feltételekkel. Eközben kis méretű, de nehéz QUBO példányokat oldunk meg, ami azok strukturális tulajdonságainak jobb megértéséhez is hozzájárul.