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

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-^tybit, a ten bit jest zmieniany przez dodanie modulo 2, dla dowolnych odrębnych pozycjihij. Nietrudno to dostrzec, jeśli interpretujemy

{C N O T}_{h, j} (x_{1}, \dots, x_{h}, \dots, x_{j}, \dots, x_{n}) = (x_{1}, \dots, x_{h}, \dots, x_{j} \oplus x_{h}, \dots, x_{n})

$\mathsf{CNOT}_{\!h,j} (x_1\,, \;\ldots\;, x_h\,,\; \ldots\;, x_j\,, \;\ldots\;, x_n) \;\;=\;\; (x_1\,, \;\ldots\;, x_h\,,\; \ldots\;, x_j \oplus x_h\,, \;\ldots\;, x_n)$

x_{h}

$x_h$

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 = (x_{1}, \dots, x_{n})

$\mathbf x = (x_1\,, \;\ldots\;, x_n)$

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).

— Niel de Beaudrap
źródło

Przypuszczam, że obliczanie determinant mod

jest również ⊕L-całkowite, stąd mod eliminacji Gaussa

⊕L-trudny.

2

$2$

2

$2$

— Emil Jeřábek 3.0

@ 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,

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

@ 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

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

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

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

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

M = \prod_{j = m}^{1} \prod_{i = 0}^{j - 1} E_{i, j} (M_{i, j}),

$M=\prod_{j=m}^1\prod_{i=0}^{j-1}E_{i,j}(M_{i,j}),$

E_{i, j} (a)

$E_{i,j}(a)$

a

$a$

i

$i$

j

$j$

\oplus L

$\oplus L$ przypadku obliczenia są modulo

2

$2$

F_{2}

$\mathbb F_2$

E_{i, j} (0) = I

$E_{i,j}(0)=I$

E_{i, j} (1)

$E_{i,j}(1)$

# L

$\#L$

k

$k$

{M o d}_{k} L

$\mathrm{Mod}_kL$ -complete problem.

— Emil Jeřábek 3.0
źródło

I mean, it is

# L

$\#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

F_{2}

$\mathbb F_2$ , 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,