ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ КВАНТОВЫХ АЛГОРИТМОВ НА ЗАДАЧЕ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ MAXCUT

Аннотация

Мураль Д.В., Мартыненко Т.В. Исследование эффективности квантовых алгоритмов на задаче комбинаторной оптимизации MaxCut. В статье представлен сравнительный анализ квантовых и классических алгоритмов для решения задачи максимального разреза графа. Эксперимент проведён с использованием квантовых алгоритмов QAOA и VQE на платформе Qiskit. В качестве классических методов использовались жадный алгоритм, симулированный отжиг и рандомизированный локальный поиск. Исследование охватывает графы с разным числом рёбер и соответствующим количеством кубитов.

Abstract

Mural D.V., Martynenko T.V., Investigation of the Efficiency of Quantum Algorithms on the MaxCut Combinatorial Optimization Problem. The article presents a comparative analysis of quantum and classical algorithms for solving the maximum cut problem in graphs. The experiment was conducted using the quantum algorithms QAOA and VQE on the Qiskit platform. Classical methods included the greedy algorithm, simulated annealing, and randomized local search. The study covers graphs with varying numbers of edges and corresponding numbers of qubits.

Ключевые слова

квантовые алгоритмы, комбинаторная оптимизация, MaxCut, QAOA, VQE, Qiskit.

Keywords

quantum algorithms, combinatorial optimization, MaxCut, QAOA, VQE, Qiskit.

Актуальность и постановка задачи MaxCut

Комбинаторные задачи оптимизации широко распространены в различных прикладных областях — от логистики и проектирования до анализа сетей и теории расписаний. Одной из фундаментальных NP-полных задач, обладающей широкой практической значимостью, является задача максимального разреза графа (MaxCut), суть которой заключается в разбиении множества вершин неориентированного графа на два подмножества таким образом, чтобы максимизировать число ребер между ними.

Классические алгоритмы решения задач такого рода, включая жадные эвристики, локальный поиск и методы стохастической оптимизации, демонстрируют хорошую производительность на малых и средних графах, но зачастую сталкиваются с экспоненциальным ростом вычислительных затрат при увеличении размерности задачи. В связи с этим особый интерес вызывает использование квантовых вычислений, которые потенциально способны обеспечивать экспоненциальное ускорение для некоторых классов задач.

Одними из наиболее перспективных квантовых подходов к решению комбинаторных задач являются квантовый алгоритм приближенной оптимизации (QAOA) и квантовый вариационный алгоритм (VQE). Несмотря на активное развитие данных методов, открытым остается вопрос об их практической эффективности на задачах умеренного размера в сравнении с классическими алгоритмами.

Цель данной работы — провести экспериментальное сравнение эффективности квантовых и классических алгоритмов при решении задачи MaxCut на графе. В рамках исследования анализируются пять различных методов: QAOA, VQE, жадный алгоритм, симулированный отжиг и рандомизированный локальный поиск. Сравнение проводится по двум основным метрикам — качеству полученного решения (числу найденных ребер) и времени выполнения. Полученные результаты позволяют оценить текущее положение квантовых алгоритмов по сравнению с классическими подходами и наметить перспективные направления дальнейших исследований.

Обзор алгоритмов квантовой оптимизации

Квантовый алгоритм приближенной оптимизации (QAOA)

QAOA — это гибридный квантово-классический алгоритм, предназначенный для приближённого решения задач дискретной оптимизации. Алгоритм строит квантовое состояние, в котором поочерёдно применяются два типа унитарных операторов: один — в соответствии с функцией цели (гамильтониан задачи), второй — для обеспечения переходов между состояниями [1].

Алгоритм строится из p слоёв, где каждый слой включает применение оператора функции цели с параметром γ_k и оператора смешивания с параметром β_k. Оптимизация параметров проводится классическим методом с целью максимизации ожидаемого значения функции цели. Начальное состояние — равномерная суперпозиция всех возможных битовых строк:

\[|s\rangle = |+\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} |x\rangle\]

где n — количество кубитов. Квантовое состояние после применения p слоёв QAOA записывается как:

\[|\psi(\gamma, \beta)\rangle = U(B, \beta_p)U(C, \gamma_p) \ldots U(B, \beta_1)U(C, \gamma_1)|s\rangle\]

где: U(C, γ) = exp(-iγC), U(B, β) = exp(-iβB), а C — гамильтониан задачи, B — гамильтониан смешивания. Для задачи MaxCut на графе G = (V, E) гамильтониан задачи имеет вид:

\[C = \sum_{(i,j)\in E} \frac{1}{2} (I - \sigma_z^i \sigma_z^j)\]

где σ_zⁱ — оператор Паули Z, действующий на кубите i, а I — единичный оператор. Цель алгоритма — максимизировать ожидаемое значение гамильтониана задачи:

\[\max_{\gamma,\beta} \langle \psi(\gamma, \beta) | C | \psi(\gamma, \beta) \rangle\]

Рис. 1. Схема слоя QAOA для четырёх кубитов

Квантовый вариационный алгоритм (VQE)

VQE — гибридный квантово-классический алгоритм, предназначенный для нахождения минимального собственного значения гамильтониана, что соответствует оптимальному решению задачи оптимизации (в том числе MaxCut). VQE строит параметризованное квантовое состояние, параметры которого оптимизируются классическим методом для минимизации энергии [3].

Основное отличие VQE от QAOA — в произвольном виде параметризованного квантового состояния, который выбирается заранее и может состоять из вращений и запутывающих вентилей, а не из фиксированного чередования операторов функции цели и смешивания.

Начальное состояние — обычно |0⟩^⊗n, параметризованное состояние:

\[|\psi(\theta)\rangle = U(\theta)|0\rangle^{\otimes n}\]

где U(θ) – унитарный оператор, зависящий от вектора параметров θ=(θ₁,θ₂,…,θ_m), n — число кубитов. Цель VQE — минимизировать ожидаемое значение гамильтониана задачи:

\[\min_{\theta} \langle \psi(\theta) | C | \psi(\theta) \rangle\]

где C — гамильтониан задачи:

\[C = \sum_{(i,j)\in E} \frac{1}{2} (I - \sigma_z^i \sigma_z^j)\]

Рис. 2. Схема слоя VQE для четырёх кубитов

Математическая постановка задачи

Для применения квантовых вариационных алгоритмов, таких как QAOA и VQE, задача MaxCut представляется в виде задачи минимизации (или максимизации) квантового гамильтониана. Наиболее удобной формой является гамильтониан Изинга, который можно записать следующим образом [5]:

\[C = \sum_{(i,j)\in E} \frac{1}{2} (I - \sigma_z^i \sigma_z^j)\]

где σ_zⁱ — оператор Паули Z, действующий на кубите i, а I — единичный оператор. Задача сводится к поиску квантового состояния, минимизирующего или максимизирующего ожидаемое значение этого гамильтониана, что соответствует максимальному разрезу графа G=(V,E).

В классической формулировке MaxCut задача выражается как поиск разбиения множества вершин V на два подмножества S и S', максимизирующего количество рёбер между ними:

\[C(z) = \sum_{(i,j)\in E} \frac{1}{2} (1 - z_i z_j)\]

где z_i ∈ {-1,1} — бинарная переменная, указывающая, в каком из двух подмножеств находится вершина i.

Программная реализация алгоритма и вычислительный эксперимент

Эксперимент проводился с использованием фреймфорка Qiskit, который позволяет моделировать и запускать квантовые алгоритмы на симуляторах и реальном квантовом оборудовании. Были реализованы два квантовых алгоритма — QAOA и VQE, а также классические алгоритмы: жадный (Greedy), симулированный отжиг (Simulated Annealing, SA) и рандомизированный локальный поиск (Randomized Local Search, RLS). Тестирование проводилось на случайных графах с числом рёбер от 2 до 20.

Результаты эксперимента

Качество решений

По качеству решений QAOA чаще всего превосходит VQE и классический жадный алгоритм, достигая максимально возможного числа пересечённых рёбер или близкого к нему. VQE показывает менее стабильные результаты и зачастую уступает как QAOA, так и стохастическим методам SA и RLS, которые в ряде случаев демонстрируют равное или лучшее качество решения. Жадный алгоритм стабильно показывает худшее качество на больших графах, что объясняется его жадной природой.

Рис. 3. График результативности нахождения рёбер

Время выполнения

По времени выполнения классические алгоритмы существенно быстрее: Greedy работает за доли миллисекунд, SA и RLS требуют нескольких миллисекунд, тогда как QAOA занимает от десятков миллисекунд до нескольких секунд. Вариационный алгоритм VQE существенно медленнее — время его работы достигает нескольких десятков секунд на больших графах, что связано с вычислительной сложностью процедуры оптимизации параметров.

Рис. 4. График выполнения затраченного времени на работу алгоритма

Выводы

В ходе исследования была рассмотрена задача MaxCut в контексте применения квантовых вариационных алгоритмов, в частности QAOA и VQE. Проведённый сравнительный анализ показал, что на текущем этапе развития квантовых вычислений указанные методы не обеспечивают устойчивого превосходства по времени вычислений и качеству решений по сравнению с классическими стохастическими алгоритмами при решении задач умеренной размерности.

Классические эвристические методы, такие как симуляционный отжиг и алгоритмы на основе локального поиска, демонстрируют высокую эффективность, устойчивость и вычислительную надёжность. Тем не менее, квантовые алгоритмы обладают потенциалом к улучшению за счёт дальнейшего развития как алгоритмических подходов (в частности, более эффективных схем параметризации и оптимизации), так и совершенствования квантового аппаратного обеспечения.

Таким образом, квантовые вариационные алгоритмы остаются важным направлением исследований, перспективным с точки зрения будущего масштабируемого применения к задачам комбинаторной оптимизации.