Хорошо известно, что сложность квантового запроса с ограниченной функцией функции равна . Теперь вопрос в том, что если мы хотим, чтобы наш квантовый алгоритм работал успешно для каждого входа с вероятностью а не обычным . Теперь с точки зрения какие будут соответствующие верхние и нижние границы?
Непосредственно для этой задачи достаточно запросов путем повторения алгоритма Гровера. Но из того, что я помню, это совсем не оптимально, так как даже простой алгоритм Гровера, если он выполняется аккуратно, то есть для соответствующего числа итераций, может достичь чего-то вроде всего за итераций. И, следовательно, используя это можно получить улучшение для всех . С другой стороны, я не ожидаю, что будет правильным ответом для очень маленьких .
Но мне интересно посмотреть, что можно показать в терминах зависимых верхних и нижних границ для разных диапазонов особенно когда очень мала, скажем, или для больших .
(Чтобы дать некоторый контекст, общее явление, к которому я обращаюсь, - это усиление в контексте сложности квантовых запросов.)
источник
Ответы:
Для полноты вот ответ.
Пусть обозначает сложность квантового запроса -error для вычисления функции а - это функция OR для битов, определяемая как . (Обратите внимание, что это отличается от проблемы, когда вам обещают, что вход имеет ровно 1, и цель состоит в том, чтобы найти это 1. Эта проблема может быть решена без ошибок в запросах .)Qϵ(f) ϵ f ORn n ORn(x1,…,xn)=⋁ni=1xi Θ(n−−√)
Тогда для всех ,ϵ∈[2−n,1/3]
Это следует из границ для квантовых алгоритмов малой и нулевой ошибок .
На самом деле, мы знаем что-то более общее. Для всех симметричных функций , которые являются функциями, которые зависят только от веса Хэмминга на входе, мы имеем это для всех ,f ϵ∈[2−n,1/3]
Это было показано в заметке о квантовых алгоритмах и минимальной степени полиномов с ошибками эпсилона для симметричных функций .
источник