Utiliser la puissance supplémentaire de la méthode de l'adversaire négatif

La méthode de l'adversaire négatif ( ) est un SDP qui caractérise la complexité des requêtes quantiques. Il s'agit d'une généralisation de la méthode de l'adversaire largement utilisée ( ), et surmonte les deux obstacles qui ont entravé la méthode de l'adversaire:$ADV^\pm$$ADV$

1. La barrière des tests de propriétés: si toutes les 0-instances sont loin de toutes les 1-instances alors la méthode adversaire ne peut pas prouver une borne inférieure mieux que .$\epsilon$$\Omega(1/\epsilon)$

2. La barrière de la complexité du certificat: si est la complexité du certificat des -instances, alors la méthode de l'adversaire ne peut pas prouver une borne inférieure mieux que où$C_b(f)$$b$$\sqrt{C_0(f)C_1(f)}$

Dans l'article , les auteurs construisent un exemple de fonction pour laquelle leur méthode surmonte les deux obstacles. Cependant, je n'ai pas vu d'exemples de problèmes naturels où cela a produit de nouvelles limites inférieures.$ADV^\pm$

Pouvez-vous fournir des références où la méthode de l'adversaire négatif a été utilisée pour atteindre une limite inférieure que la méthode originale n'a pas pu atteindre?

Le plus grand intérêt pour moi, ce sont les tests immobiliers. Actuellement, il existe très peu de limites inférieures pour les tests de propriétés, en fait, je n'en connais que deux ( CFMdW2010 , ACL2011 ), qui utilisent tous deux la méthode polynomiale (la première par réduction du problème de collision qui était à l'origine limitée par la méthode polynomiale). Nous savons qu'il existe des propriétés qui nécessitent des requêtes quantiques pour vérifier, pour tout calculable (en combinant les résultats dans BNFR2002 et GKNR2009 ). Pourquoi est-il si difficile d'utiliser la méthode de l'adversaire négatif pour prouver des limites inférieures sur eux?$\Theta(f(n))$$f(n) \in O(n)$$\Omega(f(n))$

Apparemment, je ne peux pas commenter donc ce sera une réponse, même si ce n'est qu'une réponse partielle.

$\Omega(N^{2/3})$$\sqrt{N}$ , donc si l'on essaie de le prouver en utilisant la méthode de l'adversaire, il devra utiliser la méthode de l'adversaire avec des poids négatifs (ce qui est optimal), ou pourquoi pas la méthode de l'adversaire multiplicatif.

Sinon, la méthode polynomiale est parfois plus facile à utiliser que les méthodes adverses car elle suffit à prouver l' existence du polynôme alors que pour la méthode adversaire, vous devez avoir explicitement une bonne matrice adversaire, et calculer sa norme d'opérateur.