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:

Tabela z Bartlett i Sanders, 2003

MOJE pytanie jest trzykrotne:

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

quantum-computing

— Chris Ferrie
źródło

Odpowiedź Chrisa Granade'a sugeruje, że wiersz KLM kolumny pomiarowej powinien być „zliczaniem fotonów, po selekcji”. Czy ktoś wie z góry, czy inne programy również wymagają ponownej selekcji?

— Chris Ferrie,

Być może głupie pytanie, ale czy fakt, że nie można pogodzić z nierównością Bella za pomocą pojedynczych fotonów i wykrycia homodyny, nie jest dowodem na to, że ostatniego wpisu tabeli nie można skutecznie symulować?

@ MateusAraújo - Najbardziej przekonujący dowód, że złożoność obliczeniowa nie ma nic wspólnego z lokalizacją, wynika z dwóch faktów: (1), że formalizm stabilizatora kubitowego można klasycznie skutecznie symulować za pomocą twierdzenia Gottesmana-Knilla, ale można naruszyć nierówność Bell względem stanów stabilizatora; (2) formalizm stabilizatora qutrit jest również klasycznie efektywnie symulowalny, ale można również znaleźć lokalną ukrytą zmienną, która go odtwarza.

— Chris Ferrie

Ryzykujesz, że odejdzie od pytania, ale: czy jest znany system, który ma lokalny model ukrytej zmiennej, ale który nie jest skutecznie symulowalny? To by mnie naprawdę zaskoczyło.

@ MateusAraújo - Myślę, że zrobi to klasyczny system chaotyczny, nie?

— Chris Ferrie

Odpowiedzi:

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 , poczynając od stanu początkowego $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 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ę liczb zajętości, tak że i dla każdego

| 1_{n} ⟩ = | 1, \dots, 1, 0, \dots, 0 ⟩ (n 1s) .

$\left|1_n\right>=\left|1,\dots,1,\ 0,\dots,0\right>\quad (n\text{ 1s}).$

m \times m

$m\times m$

(s_{1}, s_{2}, \dots, s_{m})

$(s_1, s_2, \dots, s_m)$

\sum_{i} s_{i} = n

$\sum_i s_i = n$

s_{i} \geq 0

$s_i \ge 0$

i

$i$ . (Większość z tych definicji znajduje się na stronach 18-20 A&A.)

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.

— Chris Granade
źródło

Świetna odpowiedź! Więc x w ostatniej kolumnie powinno również zawierać przypis lub, dokładniej, znaki zapytania, ponieważ nie wiemy, czy P = BQP, czy nie?

— Chris Ferrie,

Dzięki! Ostatnia kolumna jest co najwyżej hipotetyczna, ponieważ nie mamy dowodu, że P ≠ BQP. Wynik A&A jest jednym z najsilniejszych wyników, jakie widziałem w przypadku rozdzielania obliczeń klasycznych i kwantowych, ponieważ zapewnia konkretną teoretyczną złożoność konsekwencji istnienia wydajnego klasycznego symulatora. Może kolumna bardziej opisowa byłaby „konsekwencjami skutecznej klasycznej symulacji?”

— Chris Granade,

Kolejne pytanie, które prawdopodobnie zasługuje na pytanie samo: czy wiesz, czy istnieje naturalny sposób na udowodnienie, że optyka liniowa sama w sobie nie jest uniwersalna dla BQP? Czy może jest jakaś bariera, aby to udowodnić (np. Sugerując inne rzeczy, których nie umiemy pokazać, ale nadal są prawdą)?

— Abhinav

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

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.
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”).
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: wprowadź opis zdjęcia tutaj

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

— Chris Ferrie
źródło