Розв'язання задачі максимального розрізу графа за допомогою квантово-гібридного амплітудно-стохастичного алгоритму

Abstract

Запропоновано новий квантовий алгоритм під назвою «квантово-гібридний амплітудно-стохастичний алгоритм» (QASPA), призначений для наближеного розв’язання задачі максимального розрізу графа. Задача максимального розрізу полягає у поділі множини вершин на дві підмножини таким чином, щоб сумарна вага ребер, що з’єднують вершини різних підмножин, була максимальною. Дана задача є NP-складною комбінаторною проблемою. Класичні алгоритми розвʼязання займають надто багато часу виконання, в наслідок чого не є ефективними на середніх та великих графах. Наближені алгоритми розв’язання, забезпечують лише гарантоване наближення, не долаючи обмежень точності та швидкодії на великих графах. Запропонований алгоритм вирізняється простою схемою та мінімальною кількістю оптимізованих параметрів. Вхідний граф подається у вигляді матриці суміжності, після чого ваги ребер лінійно нормалізуються до фіксованих фазових кутів. Квантова схема починається з ініціалізації кожного кубіта перетворенням Адамара, що формує рівномірну суперпозицію всіх можливих розбиттів. Далі для кожної пари суміжних вершин послідовно застосовуються контрольований логічний NOT, однокубітний поворот навколо осі Y на кут, пропорційний вазі ребра, і повторний контрольований логічний NOT. У такий спосіб фазова інформація про ваги ребер кодується у квантовий стан системи. A novel quantum algorithm named the Quantum Approximate Shift-Phase Algorithm (QASPA) is proposed for the approximate solution of the Max- Cut problem. The Max-Cut problem consists in partitioning the set of vertices into two subsets in such a way that the total weight of the edges connecting vertices from different subsets is maximized. This problem is known to be NP-complete and represents a combinatorial challenge. Classical solution algorithms require excessive computational time, rendering them inefficient for medium and large graphs. Approximate solution methods offer guaranteed approximation ratios but still face significant limitations in terms of accuracy and performance on larger graphs. The proposed algorithm features a simple scheme and a minimal number of optimized parameters. The input graph is represented by an adjacency matrix, after which the edge weights are linearly normalized to fixed phase angles. The quantum circuit begins by applying a Hadamard transform to each qubit, thereby creating an equal superposition of all possible partitions. Subsequently, for each pair of adjacent vertices, a sequence comprising a controlled NOT gate, a singlequbit rotation around the Y-axis by an angle proportional to the edge weight, and a second controlled NOT gate is applied. This encodes the phase information about the edge weights into the quantum state of the system.