Ограничение разрыва между квантовой и детерминированной сложностью запросов

10

Хотя экспоненциальное разделение между сложностью квантового запроса с ограниченной ошибкой ( Q(f) ) и сложностью детерминированного запроса ( D(f) ) или сложностью рандомизированного запроса с ограниченной ошибкой ( R(f) ) известно, они применяются только к определенным частичным функциям. Если частичные функции имеют некоторые специальные структуры, то они также полиномиально связаны с D(f)=O(Q(f)9)) . Тем не менее, меня больше всего волнуют общие функции.

В классической работе было показано, что D(f) ограничена O(Q(f)6) для полных функций, O(Q(f)4) для монотонных полных функций и O(Q(f)2) для симметричные полные функции. Однако для такого рода функций известно не более квадратичного разделения (это разделение достигается ORнапример). Насколько я понимаю, большинство людей предполагают, что для полных функций мы имеем D(f)=O(Q(f)2) . При каких условиях эта гипотеза была доказана (кроме симметричных функций)? Каковы наилучшие текущие оценки сложности дерева решений с точки зрения сложности квантовых запросов для полных функций?

Артем Казнатчеев
источник

Ответы:

10

Насколько я знаю, общие границы, которые вы заявляете, по сути, самые известные. Немного изменив модель, Мидрижанис показал границу, что , где Q E ( f ) - точная квантовая сложность запроса f ; существуют также более узкие границы, известные с точки зрения односторонней ошибки (см. раздел 6 этой статьи ).D(f)=O(QE(f))3QE(f)f

С точки зрения более конкретных, но все же общих классов функций, есть статья Барнума и Сакса, в которой показано, что все функции однократного чтения для переменных имеют сложность квантового запроса Ω ( n.Ω(n)

Хотя этот прогресс был ограничен, был достигнут значительный прогресс в снижении сложности квантовых запросов для конкретных функций; подробности см. в этом обзоре (или, например, в более поздней работе Райхардта, в которой доказывается, что наиболее общая версия границы «противник» характеризует сложность квантового запроса).

Эшли Монтанаро
источник
5

Мне нравится ответ Эшли Монтанаро, но я подумал, что я бы также включил набор функций, для которых известна гипотеза.

OR

fD(f)=O(Q(f)2)


Подробности:

xS{1,...,n}y(iSyi=xi)f(y)=f(x)Cx(f)xC1(f)=maxx|f(x)=1Cx(f)f(x)=0

Q(f)bs(f)2C0(f)/2C1(f)+1D(f)C1(f)bs(f)C0(f)C1(f)

Артем Казнатчеев
источник
3

Если мы ограничимся вниманием к свойствам графа, то сможем доказать немного улучшенные границы по сравнению с общими границами, которые вы упомянули:

D(f)O(Q(f)6)O(Q(f)4)O(Q(f)2)

Ω(N1/4)NN

Ω(N1/3log1/6N)

[1] Sun, X .; Яо, AC .; Shengyu Zhang, "Свойства графа и круговые функции: насколько низка может быть сложность квантового запроса?", Вычислительная сложность, 2004. Труды. 19-я ежегодная конференция IEEE, том, номер 288 293, 21-24 июня 2004 г., doi: 10.1109 / CCC.2004.1313851

[2] Магниес, Фредерик; Сантха, Миклос; Сегеди, Марио (2005), «Квантовые алгоритмы для задачи о треугольнике», Материалы шестнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, Ванкувер, Британская Колумбия: Общество промышленной и прикладной математики, с. 1109–1117, arXiv: Quant -Ph / 0310134.

Робин Котари
источник
3

В 2015 году достигнут большой прогресс в этом вопросе.

f

Q(f)=O~(D(f)1/4).

С другой стороны, в arXiv: 1512.04016 [quant-ph] было показано, что квадратичная связь между квантовой и детерминированной сложностью запросов сохраняется, когда область функции очень мала.

Алессандро Косентино
источник