Решение общих QUBO с помощью QAOA с холодовым стартом через редукцию к Max-Cut

Quantum Approximate Optimization Algorithm (QAOA) — квантовый алгоритм, находящий приближённые решения задач комбинаторной оптимизации, особенно тех, которые можно сформулировать как Quadratic Unconstrained Binary Optimization (QUBO). В предыдущих работах изучались различные способы «холодового старта» QAOA посредством подготовки начального квантового состояния с использованием классаически полученных решений или информации; такие холодовые старты обычно позволяют QAOA достигать лучших коэффициентов приближения при значительно меньшей глубине схемы. Для задачи Max-Cut один из подходов холодового старта формирует начальное состояние из высокоразмерных векторов, получаемых в результате семи-дефинитной релаксации (semidefinite programming, SDP) соответствующего экземпляра Max-Cut. В данной работе эти семи-дефинитные холодовые старты используются для более широкого класса задач посредством стандартной редукции, отображающей любую QUBO-задачу в экземпляр Max-Cut. Мы эмпирически сравниваем этот подход с подходом «релаксации QUBO», который релаксирует непосредственно сам QUBO. В экспериментах рассматривается множество экземпляров QUBO, от случайно сгенерированных до соответствующих конкретным задачам, таким как задача коммивояжёра, задача о максимальном независимом множестве и оптимизация портфеля. Мы обнаруживаем, что наилучший выбор подхода холодового старта в значительной степени зависит от типа задачи.