Redukcja przestrzeni logów z obwodów Parity-L na obwody CNOT?

14

Pytanie.

W swoim artykule Ulepszona symulacja obwodów stabilizatora , Aaronson i Gottesman twierdzą, że symulacja obwodu CNOT jest zakończona w ⊕L (przy zmniejszeniu przestrzeni logarytmicznej). Oczywiste jest, że jest on zawarty w ⊕L ; jak zachowuje się wynik twardości?

Równoważnie: czy występuje ograniczenie przestrzeni logicznej z iterowanych produktów macierzy modulo 2, do iterowanych produktów macierzy elementarnych (macierzy odwracalnych, które realizują transformacje rzędowe) mod 2?

Detale

Operacja o kontrolowanym NIE (lub CNOT ) jest odwracalną operacją typu boolean w postaci gdziezmieniany jesttylkoj- ty bit, a ten bit jest zmieniany przez dodanie x h modulo 2, dla dowolnych odrębnych pozycjihij. Nietrudno to dostrzec, jeśli interpretujemy x = ( x 1

CNOTh,j(x1,…,xh,…,xj,…,xn)=(x1,…,xh,…,xj⊕xh,…,xn)
xh jako wektor ponad ℤ / 2ℤ, że odpowiada to elementarnemu modułowi 2 przekształcania rzędów, który możemy przedstawić za pomocą macierzy z 1s na przekątnej i pojedynczym położeniem nie przekątnym. Obwód CNOTNastępnie produkt matrycowy składający się z produktu z elementarnych matryc tego typu.x=(x1,…,xn)

Wspomniany wyżej artykuł Aaronsona i Gottesmana (który, nawiasem mówiąc, do tego pytania, dotyczy klasy obwodów kwantowych, które można symulować w ⊕L ), zawiera rozdział o złożoności obliczeniowej. Na początku tego rozdziału opisują ⊕L w następujący sposób:

⊕L [jest] klasą wszystkich problemów, które można rozwiązać za pomocą niedeterministycznej maszyny Turinga z logarytmiczną przestrzenią, która akceptuje wtedy i tylko wtedy, gdy łączna liczba ścieżek akceptacji jest nieparzysta. Ale istnieje inna definicja, która jest prawdopodobnie bardziej intuicyjna dla nie-informatyków. Chodzi o to, że ⊕L jest klasą problemów, które sprowadzają się do symulacji wielomianowego obwodu CNOT, tj.  Obwodu złożonego całkowicie z bramek NOT i CNOT, działających na stan początkowy | 0 ... 0⟩. (Łatwo jest wykazać, że dwie definicje są równoważne, ale wymagałoby to od nas wyjaśnienia, co oznacza zwykła definicja!)

Grupą docelową tego artykułu była znaczna liczba nie-informatyków, więc chęć objęcia stanowiska nie jest nieuzasadniona; Mam nadzieję, że ktoś może wyjaśnić, na czym polega ta równoważność.

Oczywiście symulację iloczynu takich macierzy można wykonać w ⊕L jako szczególny przypadek oceny współczynników iterowanych produktów macierzy (mod 2), co stanowi kompletny problem (przy zmniejszeniu przestrzeni logicznej) dla ⊕L . Ponadto, ponieważ macierze CNOT po prostu wykonują elementarne operacje na wierszach, dowolna odwracalna macierz może zostać rozłożona na iloczyn macierzy CNOT. Jednak: nie jest dla mnie jasne, jak rozłożyć nawet mod odwracalnej macierzy 2 na produkt macierzy CNOT przez zmniejszenie przestrzeni logicznej . (Rzeczywiście, jak zauważył Emil Jeřábek w komentarzach, eliminacja Gaussa wystarcza do obliczenia wyznaczników mod 2, co stanowi problem uzupełniający ⊕L : więc bezpośredni atak poprzez rozkład np.  odwracalnych macierzy, ponieważ produkty macierzy elementarnych wydają się niemożliwe do wykonania w przestrzeni logicznej, chyba że L  =  ⊕L .) Nie mówiąc już o produktach macierzy, które nie są odwracalne. Tak więc wydaje się, że konieczne jest pewne sprytniejsze ograniczenie.

Mam nadzieję, że ktoś może przedstawić szkic tej redukcji lub odniesienie ( np.  Tekst, dla którego jest to ćwiczenie, jeśli jest proste).

cc.complexity-theory counting-complexity linear-algebra logspace Niel de Beaudrap
źródło
2
Przypuszczam, że obliczanie determinant mod jest również ⊕L-całkowite, stąd mod eliminacji Gaussa 2 ⊕L-trudny. 22
Emil Jeřábek 3.0
1
@ EmilJeřábek: Zastanawiam się nad twoją uwagą i staram się sprawdzić, czy natychmiast oznacza to, że symulacja obwodów CNOT nie jest ukończona dla ⊕L, chyba że L = ⊕L . (Rozważ iloczyn jednej macierzy lub iloczynu jednej macierzy z macierzą tożsamości!) Wydaje się to prawie zbyt łatwe; czy coś mi brakuje? Przypuszczam, że może to wyklucza jedynie redukcje wiele do jednego.
Niel de Beaudrap,
1
Nie sądzę, że to takie proste. ⊕L jest klasą problemów decyzyjnych, podczas gdy mnożenie macierzy przez F_2 jest problemem funkcji. Wersja ⊕L mnożenia macierzy polega na pytaniu o konkretny bit wyniku (powiedzmy, górny lewy wpis macierzy). Czy może istnieć algorytm przestrzeni logicznej, który pobiera sekwencję macierzy i tworzy sekwencję macierzy elementarnych, aby produkty obu sekwencji miały ten sam lewy górny element? Jest to znacznie słabsza niż prawdziwa eliminacja Gaussa. W rzeczywistości twierdzenia Aaronsona i Gottesmana wydają mi się wiarygodne, chociaż nie jestem pewien, jak to udowodnić.
Emil Jeřábek 3.0
1
@ EmilJeřábek: Myślę o tym, w jaki sposób większość problemów decyzyjnych ⊕L opiera się na weryfikacji poszczególnych współczynników problemów, które są naturalne dla DET (często mówi się o problemach z funkcjonowaniem jako o ⊕L-ukończeniu , jednak jest to nadużycie to znaczy terminologia); i moją intuicją w przypadku produktów matrycowych jest to, że jest wystarczająco skomplikowane, że trudno jest ustalić ad-hoc, dla dowolnego pojedynczego współczynnika, że ​​dwa produkty matrycowe powinny być równe dla tego współczynnika w taki sposób, że nie można być całkiem pewnym że wszystkie pozostałe współczynniki również się zgodzą.
Niel de Beaudrap
2
Rozumiem: liczenie akceptacji ścieżek maszyny obszaru logicznego równa się liczeniu ścieżek na wykresie acyklicznym , który można przedstawić poprzez pomnożenie górnych trójkątnych macierzy przez 1 na przekątnej. To ostatnie można łatwo wyrazić jako iloczyn macierzy elementarnych w wyraźny sposób, bez eliminacji Gaussa.
Emil Jeřábek 3.0

Odpowiedzi:

9

Zacznijmy od pełnego problemu zliczania mod 2 liczby ścieżek długości n od wierzchołka s do wierzchołka t na wykresie skierowanym G = ( V , E ) . Stosujemy kilka ograniczeń przestrzeni logicznej w następujący sposób.⊕L2nstG=(V,E)

Niech będzie takim wykresem, że V ′ = V × { 0 , … , n } i E ′ = { ( ( u , i ) , ( v , i + 1 ) : i < n , ( u , v ) ∈ E } ∪ { wG′=(V′,E′)V′=V×{0,…,n} (tzn. bierzemy n + 1 kopiiwierzchołków G , powodujemy, że krawędzie przechodzą od i- tej kopii do ( i + 1 ) kopii zgodnie zkrawędziami G i dodajemy wszystkie pętle własne ). Zatem pierwotny problem jest równoważny zliczaniu ścieżek o długości n od s ′ = ( s , 0 ) do t ′ = ( t G ′E′={((u,i),(v,i+1):i<n,(u,v)∈E}∪{(w,w):w∈V′}n+1Gi(i+1)Gns′=(s,0)t′=(t,n)w .G′

Ponadto, jest acykliczny, możemy jednoznacznie określić wyliczenie V ' = { W k : k ≤ m } tak, że wszystkie krawędzie w G ' oprócz własny pętle przejść z W k aby w l jakiegoś k < l . Bez utraty ogólności, w 0 = s ′ i w m = t ′ . Niech M będzie macierzą przylegania G ′G′V′={wk:k≤m}G′wkwlk<lw0=s′wm=t′MG′ wrt danego wyliczenia. Następnie jest górną trójkątną macierzą liczb całkowitych z 1 na przekątnej, a liczba ścieżek długości n od s ′ do t ′ jest równa prawemu górnemu elementowi MM1ns′t′Mn .

M=∏j=m1∏i=0j−1Ei,j(Mi,j),
Ei,j(a)aij⊕L przypadku obliczenia są modulo2F2Ei,j(0)=IEi,j(1)#LkModkL-complete problem.
Emil Jeřábek 3.0
źródło
1
I mean, it is #L-complete for elementary matrices with nonnegative integer coefficients. With arbitrary integers, it is DET-complete.
Emil Jeřábek 3.0
The following is probably standard, but I hadn't explicitly seen it before: to show that finding the number of paths of length precisely n in a (possibly cyclic) digraph is ⊕L-complete, note that this amounts to computing coefficients of some power of an arbitrary matrix over F2, which is ⊕L-complete. This answer is then essentially as a reduction from matrix powering (using a standard construction of M as a block matrix consisting only of copies of the arbitrary adjacency matrix of G in the upper off-diagonal blocks, and 1 on the diagonal) to CNOT circuits. Nice answer!
Niel de Beaudrap
You don’t need to go through matrix powering, whose ⊕L-completeness is harder to prove. ⊕L is defined by counting mod 2 the accepting paths of a nondeterministic logspace Turing machine (with polynomial time clock, I presume, so that the number is guaranteed to be finite), which is the same as counting paths in the configuration graph of the machine (it is easy to arrange that the paths all end in the same configuration, and that the paths have the same length, by making the machine go into a loop until its clock expires and then enter a fixed accepting state).
Emil Jeřábek 3.0
Przypuszczam, że skupiając się na ideach zawartych w artykule Struktura i znaczenie klas Logspace-MOD autorstwa Buntrocka i in. , Przyzwyczaiłem się do myślenia w kategoriach liczby ścieżek o dowolnej długości w acyklicznym digrafie oraz problemów podobnych do DET , takich jak produkty matrycowe i moce, które są z nim naturalnie związane.
Niel de Beaudrap,