W jaki sposób papier BosonSampling unika łatwych klas złożonych matryc?

W złożoności obliczeniowej optyki liniowej ( ECCC TR10-170 ) Scott Aaronson i Alex Arkhipov twierdzą, że jeśli komputery kwantowe mogą być skutecznie symulowane przez klasyczne komputery, hierarchia wielomianowa upadnie na trzeci poziom. Problemem motywującym jest próbkowanie z rozkładu określonego przez sieć liniowo-optyczną; rozkład ten można wyrazić jako stały dla określonej macierzy. W klasycznym przypadku wszystkie wpisy w macierzy są nieujemne, a zatem istnieje probabilistyczny algorytm czasu wielomianowego, jak pokazali Mark Jerrum, Alistair Sinclair i Eric Vigoda (JACM 2004, doi: 10.1145 / 1008731.1008738). W przypadku kwantowym wpisy są liczbami zespolonymi. Należy zauważyć, że w ogólnym przypadku (gdy nie wymaga się, aby wpisy były nieujemne), wartości stałej nie można aproksymować nawet przy stałym współczynniku, zgodnie z klasycznym wynikiem Valiant z 1979 roku.

Artykuł definiuje rozkład zdefiniowany przez macierz A i problem z próbkowaniem$D_A$$A$

BosonSampling
Wejście: macierz Próbka: z rozkładu D $A$
$D_A$

Wykorzystanie wyniku twardości wydaje się słabym dowodem na rozdzielenie światów klasycznego od kwantowego, ponieważ możliwe jest, że klasa macierzy w określonym układzie kwantowym będzie miała szczególną formę. Mogą mieć skomplikowane wpisy, ale wciąż mogą mieć wiele struktur. Mogłaby zatem istnieć wydajna procedura próbkowania takich matryc, nawet jeśli ogólny problem to # P-trudny.

W jaki sposób użycie BosonSampling w artykule pozwala uniknąć łatwych zajęć?

Artykuł wykorzystuje dużo tła, którego nie mam w kwantowej złożoności. Biorąc pod uwagę wszystkich ludzi kwantowych na tej stronie, naprawdę doceniłbym wskaźnik we właściwym kierunku. Jak podtrzymałyby się te argumenty, gdyby odkryć, że klasa macierzy o złożonej wartości widziana w konkretnym układzie eksperymentalnym faktycznie odpowiada klasie rozkładów, z której łatwo było próbkować? A może jest coś nieodłącznego w układzie kwantowym, który gwarantuje, że to się nie stanie?

Dziękuję za twoje pytanie! Istnieją dwie odpowiedzi, w zależności od tego, czy interesują Cię wyniki twardości dla dokładnego lub przybliżonego BosonSampling.

W tym konkretnym przypadku udowodnimy, że przy dowolnej macierzy zespolonej A n-na-n można zbudować eksperyment optyczny, który daje konkretne wyniki z prawdopodobieństwem proporcjonalnym do | Per (A) | ² . To z kolei oznacza, że ​​żaden klasyczny algorytm czasu wielomianowego nie może próbkować z dokładnie takiego samego rozkładu jak eksperyment optyczny (podany opis eksperymentu jako dane wejściowe), chyba że P ^#P = BPP ^NP . W rzeczywistości możemy to wzmocnić, aby uzyskać pojedynczy rozkład D _n (zależny tylko od długości wejściowej n), który można próbkować za pomocą eksperymentu optycznego o wielkości poli (n), ale którego nie można próbkować klasycznie w poli (n ), chyba że P ^#P = BPP ^NP .

W przybliżonym przypadku sytuacja jest bardziej skomplikowana. Nasz główny wynik mówi, że jeśli istnieje klasyczny algorytm czasu wielomianowego, który symuluje eksperyment optyczny nawet w przybliżeniu (w sensie próbkowania z rozkładu prawdopodobieństwa na wyjściach, które 1 / poli (n) -zamknij w odległości zmienności), to w BPP ^NP , możesz w przybliżeniu | Per (A) | ² , z dużym prawdopodobieństwem w stosunku do macierzy n-na-n Aid Gaussa ze średnią 0 i wariancją 1.

Możemy przypuszczać, że powyższy problem jest # P-twarde (przynajmniej nie w BPP ^NP ), a strony 57-82 z naszej pracy są o dowody dla tego przypuszczenia.

Oczywiście, być może nasza hipoteza jest nieprawdziwa i faktycznie można podać algorytm wieloczasowy w celu przybliżenia stałych macierzy iid Gaussa. To byłby fenomenalny wynik! Jednak głównym celem 85% pracy, którą wykonaliśmy, było oparcie wszystkiego na hipotezie twardości, która była tak czysta, prosta i „bez kwantowa”, jak to tylko możliwe. Innymi słowy, zamiast założenia

„przybliżenie stałych niektórych dziwnych, specjalnych matryc, które powstają w naszym eksperymencie, jest trudne do wykonania”

pokazujemy, że wystarczy założyć

„aproksymowanie stałych macierzy iid Gaussa jest trudne do #P”.