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
BosonSampling
Wejście: macierz Próbka: z rozkładu 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?
źródło