Вариационный квит-эффективный эвристический алгоритм для MaxCut

Почему маленькие квантовые чипы важны для крупных задач

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

Разделение сети на две полезные части

MaxCut формулируется просто: если у вас есть набор точек (вершин), соединённых линиями (рёбрами), как следует раскрасить каждую вершину, скажем в синий или белый, чтобы как можно больше рёбер соединяли вершины разных цветов? Лучшее такое разбиение полезно в областях вроде проектирования схем и статистической физики, но найти его точно очень сложно при большом размере сети. Широко используемый классический подход, алгоритм Гоэманс–Уильямсон (GW), делает хитрое ослабление задачи и гарантированно находит разрез по крайней мере примерно на 88% от оптимального. Квантовые вычисления обещают новые способы решения таких задач, но современные устройства шумные и ограничены по размеру, что затрудняет выполнение больших глубоких схем.

Решение больших графов с помощью только нескольких квбитов

Стандартные квантовые подходы, такие как Квантовый алгоритм приближённой оптимизации (QAOA), требуют по одному квбиту на вершину, так что граф из 1000 вершин потребовал бы 1000 квбитов — далеко за пределами возможностей сегодняшних устройств. Новый метод, названный Qubit-Efficient MaxCut (QEMC), переворачивает эту зависимость: он использует лишь примерно логарифм числа вершин, то есть 11 квбитов могут кодировать информацию о более чем 2000 вершинах. Вместо привязки каждого квбита к одной вершине QEMC использует всё квантовое состояние как компактное адресное пространство и сопоставляет вершины с разными базисными состояниями этого небольшого регистра. Такая экономия квбитов делает схемы неглубокими и легче реализуемыми на шумном оборудовании, одновременно позволяя представлять очень большие графы.

Окраска вершин по вероятности вместо жёстких состояний

Ключевое новшество — способ, которым QEMC кодирует «цвет» каждой вершины. Вместо того чтобы заставлять каждую вершину быть точно синей или белой в одном квантовом состоянии, метод позволяет определять цвет вершины по вероятности её обнаружения при измерении. Вершина, чьё базисное состояние появляется с низкой вероятностью, считается одного цвета; вершина с более высокой вероятностью — другого. Пороговое значение разделяет эти два режима. Это означает, что многие разные квантовые состояния соответствуют по сути одному и тому же разбиению графа. Функция стоимости, которую минимизирует QEMC, сконструирована так, чтобы поощрять смежные вершины оказываться по разные стороны порога вероятности, что способствует увеличению числа рёбер, пересекающих две цветовые группы, и, следовательно, улучшает разрез.

Тестирование на реальных и моделированных машинах

Авторы проверяют QEMC в двух направлениях: на реальных квантовых процессорах и на классических симуляциях квантовых схем. На небольших регулярных графах до 32 вершин (используя всего 2–5 квбитов) QEMC на сверхпроводящем оборудовании IBM находит разрезы, которые совпадают или почти совпадают с лучшими ответами, полученными полным перебором, явно превосходя случайные предположения и предыдущие квантовые исследования на базе QAOA. В безшумных симуляциях QEMC стабильно достигает более 97% от оптимального разреза для этих небольших графов. Сила кодирования становится ещё более заметной для больших графов: для 9-регулярных графов до 2048 вершин классические симуляции QEMC всё ещё превосходят GW по средним и лучшим разрезам на несколько процентов, и аналогичные преимущества наблюдаются на случайных графах из 128 вершин при разных плотностях.

Скорость, ограничения и квантово-вдохновлённый потенциал

Несмотря на успех, QEMC пока не даёт формального квантового ускорения. Поскольку он использует лишь около log N квбитов, классическая симуляция его схем также масштабируется примерно линейно по числу вершин, а время, необходимое для оценки функции стоимости, растёт с числом рёбер. Эмпирические исследования показывают, что общее время до достижения уровня производительности GW растёт примерно квадратично с размером графа, что всё ещё остаётся практичным для многих задач. Это означает, что QEMC в нынешней форме скорее выступает как мощная квантово-вдохновлённая эвристика, чем как доказательство квантового преимущества.

Что это исследование означает для будущего

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

Цитирование: Tene-Cohen, Y., Kelman, T., Lev, O. et al. A Variational Qubit-Efficient MaxCut Heuristic Algorithm. npj Quantum Inf 12, 50 (2026). https://doi.org/10.1038/s41534-026-01186-2

Ключевые слова: MaxCut, квантовая оптимизация, вариационные алгоритмы, разделение графа, квантово-вдохновлённые вычисления