Есть ли какие-либо доказательства того, что линиал Шрайбмана, нижний предел сложности квантовой связи, не является жестким?

11

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

Граница факторизации (также называемая границей ), о которой я говорю, - это теорема 13 Линиала, Шрайбман, 2008 . Фактически, эта оценка вытекает из сокращения сложности квантовой коммуникации к предвзятости в игре XOR для двух игроков Degorre, et al. 2008 . По этой причине можно ожидать, что это будет паршивая граница, поскольку игра XOR даже не имеет никакого отношения к общению. Для нетерпеливых краткий обзор дан в некоторых слайдах Троем Ли .γ2

Во вводном тексте Jain, Klauck 2010 говорится, что теоретико-информационные методы могут предложить некоторую конкуренцию, но неизвестно , превосходят ли они границу . Таким образом, казалось бы, по крайней мере, несколько лет назад γ 2 был лучшим методом. Но я хотел бы знать, есть ли даже конкретный пример функции, которая, как полагают, имеет квантовую сложность связи, намного превышающую границу γ 2 .γ2γ2γ2

Дэн Шталке
источник
для полноты вы можете предоставить ссылку на результат?
Суреш Венкат
1
@SureshVenkat: я добавил несколько ссылок и контекст.
Дэн Штальке
2
+1. Это именно тот вопрос, который я не знаю, где спросить, если CSTheory не существует.
Робин Котари

Ответы:

6

γ2γ2

γ2

Маркос Вильягра
источник
Спасибо. Я не слышал об этом аспекте.
Дэн Шталке,
γ2
@RobinKothari, да, все верно. Поскольку стоимость связи QCMA ниже, чем связь BQP, нам нужна верхняя граница QCMA и (более жесткая) нижняя граница BQP.
Маркос Вильягра
а может они одинаковые?
Маркос Вильягра
1
@MarcosVillagra: я не понимаю. Дополнение Disjointness находится в NP, и, следовательно, в QCMA. Однако дизъюнктность (или ее дополнение) имеет сильную экспоненциальную нижнюю границу сложности квантовой связи. Разве это не разделяет BQP и QCMA?
Робин Котари