Usando el poder extra del método adversario negativo

El método negativo del adversario ( ) es un SDP que caracteriza la complejidad de la consulta cuántica. Es una generalización del método adversario ampliamente utilizado ( A D V ) y supera las dos barreras que obstaculizaron el método adversario:$ADV^\pm$$ADV$

1. La barrera de la prueba de propiedad: si todas las instancias 0 son lejos de todas las instancias 1, entonces el método adversario no puede probar un límite inferior mejor que Ω ( 1 / ϵ ) .$\epsilon$$\Omega(1/\epsilon)$

2. La barrera de la complejidad del certificado: si es la complejidad del certificado de lasinstancias b, entonces el método adversario no puede probar un límite inferior mejor que$C_b(f)$$b$ donde$\sqrt{C_0(f)C_1(f)}$

En el artículo original de ,$ADV^\pm$ los autores construyen una función de ejemplo para la cual su método supera ambas barreras. Sin embargo, no he visto ejemplos de problemas naturales en los que esto haya producido nuevos límites inferiores.

¿Puede proporcionar alguna referencia en la que se utilizó el método adversario negativo para lograr un límite inferior que el método original no pudo alcanzar?

El mayor interés para mí está en las pruebas de propiedad. Actualmente, existen muy pocos límites inferiores en las pruebas de propiedad, de hecho, solo conozco dos ( CFMdW2010 , ACL2011 ), que utilizan el método polinomial (el primero por reducción del problema de colisión que originalmente estaba limitado por el método polinomial). Sabemos que hay propiedades que requieren consultas cuánticas para verificar, para cualquier f ( n ) ∈ O ( n ) computable (combinando los resultados en BNFR2002 y GKNR2009$\Theta(f(n))$$f(n) \in O(n)$ ) . ¿Por qué es tan difícil usar el método de adversario negativo para probar límites más bajos en ellos?$\Omega(f(n))$

Aparentemente, no puedo comentar, por lo que esta será una respuesta, incluso si es solo una respuesta parcial.

Element-distinción tiene un límite inferior de y su complejidad certificado es $\Omega(N^{2/3})$$\sqrt{N}$ , entonces si uno trata de demostrarlo usando el método adversario, necesitaría usar el método adversario con pesos negativos (que es óptimo), o por qué no el método adversario multiplicativo.

De lo contrario, el método polinómico es a veces más fácil de usar que los métodos adversarios, ya que es suficiente para demostrar la existencia de polinomios, mientras que para el método adversario, debe tener explícitamente una buena matriz adversaria y calcular su norma de operador.