Mit der zusätzlichen Kraft der negativen Gegner-Methode

Die negative Gegnermethode ( ) ist eine SDP, die die Komplexität von Quantenabfragen charakterisiert. Es ist eine Verallgemeinerung der weit verbreiteten Gegner-Methode ( A D V ) und überwindet die beiden Hindernisse, die der Gegner-Methode im Wege standen:$ADV^\pm$$ADV$

1. Die Eigenschaftstestbarriere: Wenn alle 0-Instanzen weit von allen 1-Instanzen entfernt sind, kann die gegnerische Methode keine Untergrenze nachweisen, die besser als Ω ( 1 / ϵ ) ist .$\epsilon$$\Omega(1/\epsilon)$

2. Die Zertifikatskomplexitätsbarriere: Wenn die Zertifikatskomplexität von b- Instanzen ist, kann die gegnerische Methode keine Untergrenze nachweisen, die besser als $C_b(f)$$b$ wobei$\sqrt{C_0(f)C_1(f)}$

In dem ursprünglichen Papier$ADV^\pm$ konstruieren , um die Autoren ein Beispiel für die Funktion , ihre Verfahren beiden Barrieren überwinden. Ich habe jedoch keine Beispiele für natürliche Probleme gesehen, bei denen dies zu neuen Untergrenzen geführt hat.

Können Sie Referenzen angeben, bei denen die negative Gegnermethode verwendet wurde, um eine Untergrenze zu erreichen, die die ursprüngliche Methode nicht erreichen konnte?

Das größte Interesse für mich ist das Testen von Immobilien. Derzeit gibt es nur sehr wenige Untergrenzen für Eigenschaftstests. Tatsächlich kenne ich nur zwei ( CFMdW2010 , ACL2011 ), die beide die Polynommethode verwenden (die erste durch Reduktion des Kollisionsproblems, das ursprünglich durch die Polynommethode untergrenzen wurde). Wir wissen, dass es Eigenschaften gibt, für die Quantenabfragen erforderlich sind, um zu berechnen, ob f ( n ) ∈ O ( n ) (durch Kombinieren der Ergebnisse in BNFR2002 und GKNR2009)$\Theta(f(n))$$f(n) \in O(n)$). Warum ist es so schwierig, mit der negativen Gegnermethode die unteren Grenzen von zu beweisen ?$\Omega(f(n))$

Anscheinend kann ich keinen Kommentar abgeben, daher ist dies eine Antwort, auch wenn es sich nur um eine Teilantwort handelt.

$\Omega(N^{2/3})$$\sqrt{N}$

Andernfalls ist es manchmal einfacher, die Polynommethode als die gegnerischen Methoden zu verwenden, da dies ausreicht, um die Existenz des Polynoms zu beweisen, wohingegen Sie für die gegnerische Methode explizit eine gute gegnerische Matrix benötigen und deren Operatornorm berechnen müssen.