Использование дополнительной силы метода отрицательного противника

Метод отрицательного противника ( ) - это SDP, характеризующий сложность квантового запроса. Это обобщение широко используемого метода противника ( A D V ), и оно преодолевает два барьера, мешающих противнику:$ADV^\pm$$ADV$

1. Барьер тестирования свойств: если все 0-экземпляры находятся на расстоянии от всех 1-экземпляров, то метод противника не может доказать нижнюю границу лучше, чем Ω ( 1 / ϵ ) .$\epsilon$$\Omega(1/\epsilon)$

2. Барьер сложности сертификата: если является сложностью сертификата b- экземпляров, то метод противника не может доказать нижнюю границу лучше, чем $C_b(f)$$b$ где$\sqrt{C_0(f)C_1(f)}$

В оригинальной бумаге$ADV^\pm$ авторы построить пример функции , для которой их метод преодолевает оба барьеров. Однако я не видел примеров каких-либо естественных проблем, когда это давало новые нижние оценки.

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

Самый большой интерес для меня - это тестирование недвижимости. В настоящее время существует очень мало нижних границ при тестировании свойств, на самом деле я знаю только два ( CFMdW2010 , ACL2011 ), в которых оба используют полиномиальный метод (первый путем сокращения из задачи столкновения, которая изначально была ограничена снизу полиномиальным методом). Мы знаем, что существуют свойства, которые требуют квантовых запросов для проверки любого вычислимого f ( n ) ∈ O ( n ) (путем объединения результатов в BNFR2002 и GKNR2009$\Theta(f(n))$$f(n) \in O(n)$). Почему так трудно использовать метод отрицательного противника, чтобы доказать нижние оценки на них?$\Omega(f(n))$

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

Элемент-отчетливость имеет нижнюю грань , а его сложность сертификата $\Omega(N^{2/3})$ , поэтому, если кто-то пытается доказать это с помощью метода противника, ему нужно будет использовать метод противника с отрицательными весами (что является оптимальным), или почему бы не использовать метод мультипликативного противника.$\sqrt{N}$

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