Ограниченная глобальная оптимизация для QAOA

Алгоритм квантовой аппроксимативной оптимизации (QAOA) зарекомендовал себя как перспективный вариационный квантовый алгоритм для решения NP-трудных комбинационных задач оптимизации. Однако существенным ограничением является оптимизация его классических параметров, которая сама по себе является NP-трудной задачей. Для обхода этого препятствия предлагались эвристики инициализации, улучшённые кодирования задач и выгодные масштабирования проблем. Хотя такие стратегии дополнительно повышают производительность QAOA, они по-прежнему опираются исключительно на локальные оптимизаторы. Мы показываем, что методы локальной оптимизации по сути недостаточны в условиях сложного ландшафта целевой функции QAOA. Напротив, глобальные методы оптимизации существенно улучшают работу QAOA на различных экземплярах задач. Несмотря на то, что глобальная оптимизация обычно требует большого числа оценок целевой функции, мы демонстрируем, что ограниченные глобальные оптимизаторы могут обеспечить лучшую производительность без необходимости чрезмерного числа оценок целевой функции.