Алгоритмы квантового приближения

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

Под «значимым» я подразумеваю не обязательно экспоненциальный, но больший, чем для соответствующих точных алгоритмов. Другими словами, мне интересно, если ослабление требования, согласно которому наш алгоритм дает точное решение, дает значительное преимущество квантовым алгоритмам.

Комментарий обновлен до частичного ответа:

В наши дни довольно много работы над предполагаемой (или нет) квантовой версией теоремы PCP: см., Например, этот пост в блоге Скотта Ааронсона http://www.scottaaronson.com/blog/?p=139 или этот ответ Питер Шор о MathOverflow /mathpro/45106/quantum-pcp-theorem/45167#45167

Что касается алгоритмов квантовой аппроксимации, вы можете посмотреть эту ссылку "Алгоритмы аппроксимации для QMA-полных задач" http://arxiv.org/abs/1101.3884

Лично мне не известны какие-либо работы в направлении алгоритмов квантового приближения в смысле относительных приближений (против аддитивных приближений) (хотя это не обязательно означает, что они не существуют).

Обратите внимание , что если ваша цель заключается в разработке поли-время кванта прибл ALGS для, скажем, NP-трудных проблем, многие проблемы , такие как MAX-CUT уже имеют жесткий классический ALGS приблизительно (если предположить , что уникальные игры Гипотеза или от лечащего врача). Поэтому, вероятно, имеет смысл начать с изучения проблемы, в которой есть разрыв между известным соотношением аппроксимации и результатами твердости.

Другим направлением является сложность аппроксимации - см., Например, http://arxiv.org/abs/0811.3412 и http://arxiv.org/abs/1012.3319 для частичного положительного и отрицательного прогресса в отношении возможной квантовой теоремы PCP.

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

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

Приближенный алгоритм для оптимизации алгоритмов представлен здесь - В статье представлена алгоритм квантового приближения для целевой функции , которая имеет унитарную ворот , который имеет свое расположение в качестве оптимума целевой функции. Для фиксированной$i$и тот, который изменяется в зависимости от размера ввода, квантовый алгоритм находит приближение к оптимальному решению. Они изучили приложение к задачам оптимизации MaxSat и MAX-CUT (для некоторых случаев регулярных графов). Целевая функция для задачи оптимизации рассматривается как специальный унитарный оператор, который концентрирует решение и тем самым достигает аппроксимации.