Złożoność obliczeniowa optyki kwantowej

W „Wymaganiu do obliczeń kwantowych” Bartlett i Sanders podsumowują niektóre ze znanych wyników obliczeń ciągłych zmiennych kwantowych w poniższej tabeli:

MOJE pytanie jest trzykrotne:

1. Czy dziewięć lat później można wypełnić ostatnią komórkę?
2. Jeśli kolumna zostanie dodana z tytułem „Universal for BQP”, jak wyglądałaby reszta kolumny?
3. Czy 95-stronicowe arcydzieło Aaronsona i Arkhipova można streścić w nowym rzędzie?

W odniesieniu do trzeciego pytania Aaronson i Arkhipov (A&A za zwięzłość) stosują konstrukcję liniowego optycznego obliczenia kwantowego bardzo ściśle związanego z konstrukcją KLM. W szczególności rozważają przypadek identycznych niedziałających fotonów w przestrzeni trybów poli ( n ) ≥ m ≥ n , poczynając od stanu początkowego | 1 n ⟩ = | 1 , ... , 1 , 0 , ... , 0 $n$$\text{poly}(n) \ge m \ge n$ Ponadto A&A zezwala na dzielniki wiązki i przesuwniki faz, które wystarczają do wygenerowania wszystkichoperatorów jednostkowych m × m w przestrzeni trybów (co ważne, ale nie w pełnej przestrzeni stanu systemu). Pomiar przeprowadza się przez zliczanie liczby fotonów w każdym trybie, dając krotkę ( s 1 , y 2 , ... , s m ) liczb zajętości, tak że Σ I s I = n i s i ≥ 0 dla każdego

Zatem w języku tabeli model BosonSampling A&A najlepiej byłoby opisać jako „ fotonów, optyka liniowa i zliczanie fotonów”. Podczas gdy klasyczna wydajność próbkowania z tego modelu jest, ściśle mówiąc, nieznana, zdolność klasycznego próbkowania z modelu A&A oznaczałaby załamanie hierarchii wielomianowej. Ponieważ każde załamanie PH jest ogólnie uważane za wyjątkowo mało prawdopodobne, wcale nie jest trudno powiedzieć, że BosonSampling jest bardzo prawdopodobnie nieskutecznie i klasycznie symulowalny.$n$

$1/16^\Gamma$$\Gamma$

Aaronson bada później wybraną obudowę optyki liniowej w swoim kolejnym artykule na temat twardości # P wartości stałej. Ten wynik wcześniej udowodnił Valiant, ale Aaronson przedstawia nowy dowód oparty na twierdzeniu KLM. Na marginesie, uważam, że ten artykuł stanowi bardzo miłe wprowadzenie do wielu koncepcji, które A&A wykorzystują w swoim arcydziele BosonSampling.

$\cos^2(\frac\pi8)$

1. Uważam, że sprawiedliwie jest powiedzieć, że ostatni wpis w tabeli to „X” ze względu na obliczenia kwantowe z klastrami o zmiennej ciągłości autorstwa Gu i in . Pokazują, że na stany skupień niegaussowskich można oddziaływać za pomocą pomiarów homodyny dla UQC.
2. Hipotetyczna kolumna „Universal for BQP” miałaby „X” w pierwszym rzędzie i „sprawdza” resztę - z wyjątkiem hipotetycznego rzędu w wyniku Aaronsona i Arkhipova, który miałby „?” (choć według autorów jest to prawdopodobnie „X”).
3. Zobacz Chrisa Granade za odpowiedź powyżej.

AKTUALIZACJA: Powinienem był również zapytać, czy można dodać jakieś nowe wiersze. W każdym razie rzeczywiście można:

To jest z Veitch i in . Zobacz także Mari i Eisert .