Algorytmy holograficzne - równoważność zasad

10

Przeglądałem przełomowy artykuł Les Valiant i ciężko mi było spędzić czas z Propozycją 4.3 na stronie 10 tego artykułu.

Nie rozumiem, dlaczego jest tak, że jeśli istnieje generator z pewnymi wartościami dla na podstawie { ( a 1 , b 1 ) ( a r , b r ) } , to istnieje jakiś generator z tym samym v a l Wartości G dla dowolnej podstawy { ( x a 1 , y b 1 ) ( x a r , y b r )valG{(a1,b1)(ar,br)}valG ( 1 s t k i n d ) lub { ( x b 1 , Y 1 ) ... ( x b R , Y R ) } ( 2 n d k : i n d ) dla każdego X , Y F .{(xa1,yb1)(xar,ybr)}1stkind{(xb1,ya1)(xbr,yar)}2ndkindx,yF

Dzielne wskazuje na względu na poprzedzającą punkt - mianowicie rodzaju transformacji można osiągnąć przez dodanie do każdego wejścia lub wyjścia węzeł krawędź masy 1 . 2 n d rodzaju transformacji Bitny twierdzi, można osiągnąć przez dodanie do węzłów wejściowych lub wyjściowych łańcuchy o długości 2 ważone przez X i Y odpowiednio.1st12nd2xy

Tak naprawdę nie byłem w stanie zrozumieć tych stwierdzeń. Być może są już jasne, ale wciąż nie rozumiem, dlaczego powyższy konstrukt pomaga osiągnąć jakiekolwiek możliwe do zrealizowania wartości jednej podstawie z nową podstawą, która jest jednym z powyższych typów.valG

Proszę, pomóż mi je rozjaśnić. Z drugiej strony, czy są dostępne ankiety beztensorowe dla algorytmów holograficznych dostępne online. Większość z nich używa tensorów, które niestety mnie przerażają :-(

Najlepszy -Akash

Akash Kumar
źródło

Odpowiedzi:

8

Tensory (w tym sensie) to tylko tablice liczb, więc nie sądzę, że znajdziesz ankiety bez tensora, chyba że są całkowicie wolne od obliczeń.

Operacja „ ” formalizuje zarówno operacje zmiany podstawy, jak i dołączania gadżetów do każdego węzła wyjściowego (w rzeczywistości lubię myśleć o zmianie podstawy jako o rodzaju operacji gadżetowej). Niech Γ będzie klapką generatora ze standardową sygnaturą M i 1 i 2i k = u ( Γ ) . To tablica 2 tys . Liczb. Podpis na nowej podstawie nadawany jest przezTkΓMi1i2ik=u(Γ)2k

(TkM)i1i2ik:=i1,,ikTi1i1TikikMi1i2ik

gdzie to jakaś matryca dwa na dwa opisująca nową podstawę.T

Niech będzie zapałką utworzoną przez dodanie k nowych wierzchołków do Γ , przyjmując, że są to nowe wyjścia i łącząc je ze starymi wyjściami za pomocą krawędzi o wadze x . Zatem nową sygnaturą jest C k M, gdzie C i j jest macierzą ( 0 x 1 0 ) . Jeśli następnie wykonać zmianę podstawy T C - 1 można uzyskać podpis T k M .ΓkΓxCkMCij(0x10)TC1TkM

Colin McQuillan
źródło
Przepraszam za późną odpowiedź, byłem dziś zajęty. Obawiam się, że z powodu mojego ograniczonego zrozumienia tensorów nadal nie mogę cię zrozumieć. Kiedyś myślałem, że sygnatura bramki dopasowania generatora w nowej podstawie, została uzyskana z sygnatury u ( Γ ) w starej podstawie przez rozwiązanie S = S 0 do T k × S = u ( Γ ) . Myślałem, że Valiant wspomniał w swoim v a l G ( Γ , x )Su(Γ)S=S0Tk×S=u(Γ)valG(Γ,x)przykład, że właśnie zamierzał wyrazić wektor perfMatch jako sumę współczynników wrt do nowej podstawy. Nie jestem jednak pewien, ponieważ mój oczywisty brak tła z tensorami.
Akash Kumar
[cd] Ponadto, nie jestem w stanie podążać za przykładem z . Czy mógłbyś prosić o więcej rozwinięcia? Dzięki - AkashCkM
Akash Kumar
Cieszę się, że mogę to rozwinąć, ale mogę dodawać mylące notacje. Czy możesz najpierw odpowiedzieć na to pytanie: jeśli dodasz krawędzie w każdym węźle wyjściowym, jaki, twoim zdaniem, miałby to wpływ na podpis? Ponadto, że można wyrazić jako ( T - 1 ) k S - Nie pamiętam z góry, jakie rzeczywiste współczynniki T powinny być w kategoriach n 0 , n 1 , p 0 , p 1 Valianta . S0(T1)kSTn0,n1,p0,p1
Colin McQuillan
Spróbuję podać moje zamieszanie na przykładzie. Rozważmy generator, który jest ścieżką o długości 3, w której wszystkie 3 węzły są węzłami o / p. Sygnatura standardowa tego generatora to . A podpis zmodyfikowanego gadżetu z 3 nowymi węzłami, z których każdy jest podłączony do jednego węzła o / p w standardzie, to x ( 1 , 1 , 1 , 1 1 , 1 , 1 , 0 )(0,1,1,0,1,0,0,1)x(1,1,1,1 1,1,1,0). Czy możesz kontynuować ten przykład? Ja zobaczyć jak robi C = ( 0 , 1 ) T ( x = 1 , 0 ) t ustawy o u ( Γ ) . Dziękujemy za cierpliwośćC3whereC=(0, 1)t(x=1, 0)tu(Γ)
Akash Kumar,
1
P3P3Zu(P3)=(0,1,0,0,1,0,0,1)(1,0,0,1,0,0,1,0)(C3u(P3))1,2,2=1