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$

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)$
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))$

— Artem Kaznatcheev
źródło

Ω (1 / ϵ)

$\Omega(1/\epsilon)$

Ω (1 / n)

$\Omega(1/n)$

Wiem o zastosowaniu negatywnego przeciwnika w kryptografii przez Brassarda, Hoyera, Kalacha, Kaplana, Laplante i Salvaila ( iacr.org/conferences/crypto2011/abstracts/385.htm ), który pojawi się w CRYPTO'11. Wykorzystali twierdzenie o składzie, aby udowodnić lukę w grach Merkle dla kwantowego przeciwnika działającego przeciwko stronom kwantowym zmieniającym przesłanie. Niestety, nie ma jeszcze ostatecznej wersji artykułu. Może więc możesz poczekać na postępowanie lub skontaktować się z autorami.

— Marcos Villagra,

artykuł wymieniony w moim komentarzu powyżej można pobrać z arXiv ( arxiv.org/abs/1108.2316 ). W szczególności sprawdź lemat 1 i lemat 5 w dodatku.

— Marcos Villagra,

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.

— Loïck
źródło

To konkretnie nie odpowiada na pytanie. Możemy użyć dokładności metody negatywnego przeciwnika, aby wiedzieć, że pewna matryca przeciwnika MUSI istnieć w przypadku problemów takich jak rozróżnienie elementów (lub jeśli chcemy testowania właściwości, problemu kolizji). Ale tak naprawdę nie jest to metoda ujemnego przeciwnika, lecz metoda wielomianowa. Myślę, że jeśli pytanie nie jest wystarczająco jasne, powinienem je dopracować.

— Artem Kaznatcheev