Есть ли какое-либо общее утверждение о том, какие проблемы можно аппроксимировать более эффективно с помощью квантового компьютера?

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

Из ответа Блю:

Эмпирическое правило в теории сложности состоит в том, что если квантовый компьютер «может помочь» с точки зрения решения за полиномиальное время (с ошибкой), то если класс проблемы, которую он может решить, лежит в BQP, а не в P или BPP

Как это относится к аппроксимационным классам? Существует ли какое-либо конкретное топологическое, численное и т. Д. Свойство квантовых вычислений, которое можно использовать?

В качестве примера того, что я мог спросить (но определенно не ограничиваясь этим!), Возьмите алгоритм Кристофидес : он использует определенные геометрические свойства графа, на котором он оптимизируется (симметрия, неравенство треугольников): продавец путешествует по реальному миру , Но продавцы также имеют огромную массу, и мы можем знать их позицию и импульс одновременно с большой точностью. Может быть, квантовая модель могла бы также работать для других видов метрик с более смягченными ограничениями, такими как дивергенция KL ? В этом случае решение все равно будет завершено NP, но оптимизация будет применяться для более широкой топологии. Этот пример может быть длинным, но я надеюсь, вы понимаете, о чем я. Я действительно не знаю, имеет ли это смысл вообще, но ответ мог бы также обратиться к этому в этом случае :)

СВЯЗАННЫЕ С:

• Уровень преимущества отжига для коммивояжера

Quantum Примерного Алгоритм оптимизации является хорошим местом для начала анализа относительной эффективности квантовых алгоритмов на задачах аппроксимации. Один из результатов на данный момент состоит в том, что при p = 1 QAOA теоретически может достичь коэффициента аппроксимации 0,624 для MaxCut на 3-регулярных графиках. Этот результат был получен с помощью перебора всех возможных случаев. Это не метод, который легко обобщается, поэтому относительно мало известно о производительности QAOA для других проблем.

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