Wykorzystanie dodatkowej mocy metody negatywnego przeciwnika

Negatywna metoda przeciwnika ( $ADV^\pm$ ) to SDP, który charakteryzuje złożoność kwantowych zapytań. Jest to uogólnienie powszechnie stosowanej metody przeciwnika ( ) i pokonuje dwie bariery, które utrudniały metodę przeciwnika:$ADV$

1. Bariera testowania właściwości: jeśli wszystkie wystąpienia 0 są daleko od wszystkich 1 wystąpień, wówczas metoda przeciwnika nie może udowodnić dolnej granicy lepiej niż .$\epsilon$$\Omega(1/\epsilon)$

2. Bariera złożoności certyfikatu: jeśli jest złożonością certyfikatu substancji, wówczas metoda przeciwnika nie może udowodnić dolnej granicy lepiej niż gdzie$C_b(f)$$b$$\sqrt{C_0(f)C_1(f)}$

W oryginalnym artykule autorzy konstruują przykładową funkcję, dla której ich metoda pokonuje obie bariery. Nie widziałem jednak przykładów żadnych naturalnych problemów, w przypadku których spowodowało to nowe dolne granice.$ADV^\pm$

Czy możesz podać odniesienia, w których zastosowano metodę negatywnego przeciwnika, aby osiągnąć dolną granicę, której nie mogła osiągnąć metoda pierwotna?

Największym zainteresowaniem cieszą mnie testy nieruchomości. Obecnie istnieje bardzo niewiele dolnych granic testowania właściwości, w rzeczywistości znam tylko dwa ( CFMdW2010 , ACL2011 ), które oba wykorzystują metodę wielomianową (pierwsza z redukcji z problemu kolizji, która pierwotnie była dolna ograniczona metodą wielomianową). Wiemy, że istnieją właściwości, które wymagają kwantowych zapytań dla dowolnego obliczalnego (przez połączenie wyników w BNFR2002 i GKNR2009 ). Dlaczego tak trudno jest zastosować negatywną metodę przeciwnika, aby udowodnić, że na nich niższe granice?$\Theta(f(n))$$f(n) \in O(n)$$\Omega(f(n))$

Najwyraźniej nie mogę komentować, więc będzie to odpowiedź, nawet jeśli tylko częściowa.

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

W przeciwnym razie metoda wielomianowa jest czasami łatwiejsza w użyciu niż metody przeciwnika, ponieważ wystarczy udowodnić istnienie wielomianu, podczas gdy w przypadku metody przeciwnika musisz wyraźnie mieć dobrą macierz przeciwnika i obliczyć jej normę operatora.