Oddzielanie NP od BQP względem wyroczni

Patrzyłem na notatkę z wykładu, w której autor podaje wyrocznię między nimi$\mathsf{BQP}$ i $\mathsf{NP}$. Wskazuje, w jaki sposób można zastosować standardowe techniki diagonalizacji, aby uczynić to rygorystycznym.

Czy ktoś może szczegółowo opisać technikę diagonalizacji, którą należy zastosować? Intuicyjnie powinny istnieć istotne różnice między tymi, które służą do umieszczenia czegoś poza klasycznymi klasami złożoności, a tymi, które służą do umieszczenia czegoś poza$\mathsf{BQP}$. W szczególności, biorąc pod uwagę, że algorytm Grovera jest optymalny, szukam techniki diagonalizacji, abyśmy mogli zbudować wyrocznię$A$ dla którego $\mathsf{NP}^{A} \not\subseteq \mathsf{BQP}^{A}$.

Wydaje mi się, że argumenty diagonalizacji, które można zastosować, różnią się tylko nieznacznie od standardowego, np.  Takie, jakie można znaleźć w tych notatkach z wykładu na temat twierdzenia Baker – Gill – Solovay ( tj. Że istnieją wyroki dla których a także wyrocznie dla których ). Zasadniczo musisz nieco inaczej opisać „inżynierowanie” przeciwnika.$A$$\mathsf P^A = \mathsf{NP}^A$$A$$\mathsf P^A \ne \mathsf{NP}^A$

Oto w jaki sposób możemy użyć tej metody, aby udowodnić istnienie oracle , dla których . Dla dowolnej wyroczni zdefiniuj język Oczywiste jest, że z tego prostego powodu, że niedeterministyczna maszyna Turinga może sprawdzić, czy dane wejściowe mają postać dla jakiegoś , a następnie odgadnąć ciąg dla których jeśli takie istnieje. Celem jest pokazanie, że$A$$\mathsf{NP}^A \not\subseteq \mathsf{BQP}^A$$A$

$$L_A = \Bigl\{ 1^n \;\Big\vert\; \exists z \in \{0,1\}^n : A(z,0) = (z,1)\Bigr\} .$$ $L_A \in \mathsf{NP}^A$$1^n$$n$$z \in \{0,1\}^n$$A(z,0) = (z,1)$$z$$L_A$nie może być ustalony w czasie wielomianowym, z błędem ograniczonym, przez jednolitą rodzinę obwodów jednolitych, przy użyciu dolnej granicy dla problemu wyszukiwania.$O(2^{n/2})$

1. Niech będzie takie, że problem wyszukiwania na wyroczniach z wejściami bitowymi wymaga co najmniej zapytań wyroczni, aby poprawnie podjąć decyzję (z prawdopodobieństwem co najmniej 2/3), dla wszystkich .$c,N > 0$$n$$c 2^{n/2}$$n > N$
   
   

2. Niech,, będzie wyliczeniem wszystkich rodzin obwodów jednolitych wyroczni , tak że sekwencja bramki obwoduoddziaływanie na bitowych wejściach może być wytwarzane w czasie ściśle mniejszym niż . (Ten limit czasowy odnosi się do warunku „jednorodności”, w którym będziemy zainteresowani obwodami, które mogą być obliczone przez deterministyczną maszynę Turinga w czasie wielomianowym - warunek silniejszy niż tu narzucamy. Można wyliczyć te rodziny obwodów, ponieważ instancja, reprezentując je pośrednio przez deterministyczne maszyny Turinga$\mathbf C^{(1)}\!$$\mathbf C^{(2)}\!$$\ldots$$\mathbf C^{(k)} \!= \{ C^{(k)}_n \}_{n \geqslant 0 }$$C^{(k)}_n\!$$n$$c 2^{n/2}$$\mathbf T^{(k)}$ , które wywołują sekwencji brama i wymienienie tych ). W wyliczyć rodziny układu tak, że każdy obwód rodziny następuje bezstopniowo często wyliczenia.

   • Z granic wykonawczych opisu sekwencji bramek wynika w szczególności, że ma mniej niż bramek dla wszystkich , a w szczególności tworzy mniej niż zapytań do wyroczni.$C^{(k)}_n$$c 2^{n/2}$$k$$c 2^{n/2}$

   • Dla dowolnego rozważ obwód. Z dolnej granicy problemu wyszukiwania wiemy, że dla istnieją możliwe wartości funkcji oracle ocenione przez wyrocznię, takie jak że z prawdopodobieństwem 2/3 dane wyjściowe wygenerowane przezna wejściu nie jest poprawną odpowiedzią na pytanie, czy .$n$$C^{(n)}_n\!$$n > N$$f: \{0,1\}^n \to \{0,1\}$$C^{(n)}_n\!$$1^n$$\exists z \!\in\! \{0,1\}^n\!:\! f(z) \!=\! 1$

   • Dla każdego wybierz taką funkcję dla której „zawiedzie” w ten sposób.$n > N$$f_n$$C^{(n)}_n$
     
     

3. Niech będzie wyrocznią, która przy wejściach o rozmiarze ocenia .$A$$n > N$$f_{\!\!\:n\!\:}$

Po skonstruowaniu w ten sposób, każda rodzina obwodów nie poprawnie decyduje z prawdopodobieństwem co najmniej 2/3, dla niektórych (i nieskończenie wiele takich faktycznie). Wówczas żadna z rodzin obwodów poprawnie nie decyduje z prawdopodobieństwem sukcesu ograniczonym poniżej 2/3 na wszystkich wejściach, tak że nie może zostać rozwiązany z takimi granicami przez żadną jednorodną rodzinę obwodów jednolitych konstruowalną w czasie .$A$$\mathbf C^{(n)}$$L_A$$n > N$$n$$\mathbf C^{(k)}$$L_A$$L_A$$p(n)$

Tak więc, , z którego wynika, że .$L_A \notin \mathsf{BQP}^A$$\mathsf{NP}^A \not\subseteq \mathsf{BQP}^A$