Единый алгоритмический учёт сложности вычисления ожидания QAOA за постоянное число раундов Алгоритм квантовой приближённой оптимизации (QAOA) активно изучается для решения комбинаторных задач оптимизации. В статье показано, что точное вычисление ожидаемой производительности QAOA для задачи Max-Cut на общих графах является NP-сложной задачей. Предложен алгоритм динамического программирования для оценки производительности QAOA, который позволяет точно оценить производительность алгоритма в полиномиальное время при определённых условиях. arXiv: 2511.20212 Обзоры | Квантовая физика
Единый алгоритмический учёт сложности вычисления ожидания QAOA за постоянное число раундов
Алгоритм квантовой приближённой оптимизации (QAOA) активно изучается для решения комбинаторных задач оптимизации. В статье показано, что точное вычисление ожидаемой производительности QAOA для задачи Max-Cut на общих графах является NP-сложной задачей. Предложен алгоритм динамического программирования для оценки производительности QAOA, который позволяет точно оценить производительность алгоритма в полиномиальное время при определённых условиях.
arXiv: 2511.20212
