Konsekwencje ?

Chociaż twierdzenie Adlemana pokazuje, że , nie znam żadnej literatury badającej możliwe włączenie . Jakie konsekwencje teoretyczne pod względem złożoności miałoby takie włączenie? $\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}$ $\mathsf{BQP} \subseteq \mathsf{P}/\text{poly}$

Twierdzenie Adlemana jest czasem nazywane „protoplastą argumentów derandomizacji”. Uważa się, że podlega derandomizacji, podczas gdy nie ma dowodów na to, że „kwantowość” mogłaby zostać w jakiś sposób usunięta. Czy to możliwy dowód, że prawdopodobnie nie będzie w ? $\mathsf{BPP}$ $\mathsf{BQP}$ $\mathsf{BQP}$ $\mathsf{P}/\text{poly}$

— Martin Schwarz
źródło

Powiedziałbym, że nie mamy żadnego powodu, aby sądzić, że BQP jest w wersji P / poly. Mamy powody, by sądzić, że BQP nie ma P / poly, ale są one mniej więcej identyczne z naszymi powodami, aby myśleć, że BQP ≠ BPP. Na przykład, jeśli BQP⊂P / poly, faktoring jest w P / poly, co wystarczy, aby złamać wiele kryptografii zgodnie ze standardowymi definicjami bezpieczeństwa.

Ponadto, jak słusznie zauważyłeś, nie ma kwantowego analogu sztuczki Adlemana - w rzeczywistości nie ma sposobu na „wyciągnięcie kwantowości z algorytmu kwantowego”, analogicznie do tego, jak można wyciągnąć losowość z randomizowanego algorytmu. Nie sądzę więc, aby ktokolwiek zgadywał, na co powinna składać się porada P / poly dotycząca symulacji komputera kwantowego (bardziej niż przypuszczenie, powiedzmy, w przypadku NP vs. P / poli).

Ostatnia uwaga: moją pracę z Alexem Arkhipovem (i niezależną pracą Bremner-Jozsa-Shepherd) można łatwo dostosować, aby pokazać, że jeśli QUANTUM-SAMPLING jest w P / poli (OK, w „BPP-SAMPLING / poly”) , następnie P ^#P ⊂BPP ^NP / poly, a zatem hierarchia wielomianowa zapada się --- w tym przypadku, jak sądzę, do czwartego poziomu. Obecnie jednak nie wiemy, jak dostosować tego rodzaju wynik z problemów związanych z próbkowaniem do problemów decyzyjnych.

— Scott Aaronson
źródło

Dziękuję bardzo za odpowiedź, Scott! Zastanawiam się: jakie są znane wyniki dotyczące P ^ # P z poziomami PH / poli? Co właściwie wiadomo o P ^ # P vs. PH / poly? (np. czy istnieje jakaś niejednolita wersja twierdzenia Tody?). Dlaczego P ^ # P w PH / poly zwija PH / poly, jeśli nie znamy PH / poly w P ^ # P? Lub czego mi brakuje?

— Martin Schwarz

Należy tutaj uogólnić dowód twierdzenia Karp-Lipton. Na początku nie jest trudno wykazać (używając rozumowania w stylu KL), że jeśli coNP jest w NP / poly, to PH spada do 3. poziomu. Ale to powinno się relatywizować, aby pokazać, że jeśli coNP ^ NP ^ NP znajduje się w NP ^ NP ^ NP / poli, wówczas PH spada do 5. poziomu. I z pewnością P ^ # P w BPP ^ NP / poly implikuje coNP ^ NP ^ NP jest w NP ^ NP ^ NP / poli. Ale hmm, zapadam się tutaj tylko na 5 poziom! Zakładając, że jest to poprawne, czy ktoś może go poprawić do upadku na 4. poziomie? (Jeśli nie, to „najwyższe” załamanie PH, jakie kiedykolwiek widziałem!))

— Scott Aaronson

Trzeci poziom wystarczy. Zarówno i Karp – Lipton relatywizują się, więc najpierw , a po drugie, jeśli , to .

B P P \subseteq P / p o l y

$\mathrm{BPP}\subseteq\mathrm P/\mathrm{poly}$

{B P P}^{N P} / p o l y = P^{N P} / p o l y

$\mathrm{BPP}^\mathrm{NP}/\mathrm{poly}=\mathrm{P}^\mathrm{NP}/\mathrm{poly}$

Σ_{2}^{P} \subseteq {(B P) P}^{N P} / p o l y

$\Sigma^P_2\subseteq\mathrm{(BP)P}^\mathrm{NP}/\mathrm{poly}$

Σ_{3}^{P} = Π_{3}^{P}

$\Sigma^P_3=\Pi^P_3$

— Emil Jeřábek wspiera Monikę

(I różne znane wzmocnienia KL również relatywizują się w tym względzie, w szczególności powyższe założenie faktycznie zwija PH do , z wyjątkiem tego, że nigdy nie widziałem z indeksem innym niż 2, więc prawdopodobnie jest to niestandardowy zapis.)

S_{3}^{P} \subseteq Z P P^{N P^{N P}} \subseteq Σ_{3}^{P} \cap Π_{3}^{P}

$S^P_3\subseteq\mathrm{ZPP^{NP^{NP}}}\subseteq\Sigma^P_3\cap\Pi^P_3$

S^{P}

$S^P$

— Emil Jeřábek obsługuje Monikę