Holographische Algorithmen - Äquivalenz von Basen

Ich habe Les Valiants wegweisendes Papier durchgesehen und hatte es mit Proposition 4.3 auf Seite 10 des Papiers schwer.

Ich kann nicht verstehen, warum es einen Generator mit bestimmten Werten für mit einer Basis , dann gibt es einen Generator mit demselben -Werte für jede Basis $valG$ $\{(a_1,b_1) \ldots (a_r,b_r)\}$ $valG$ ( ) oder ( ) für jedes . $\{(xa_1,yb_1) \ldots (xa_r,yb_r)\}$ $1^{st} kind$ $\{(xb_1,ya_1) \ldots (xb_r,ya_r) \}$ $2^{nd} kind$ $x,y \in F$

Valiant weist auf den Grund im vorhergehenden Absatz hin - nämlich, dass die Art der Transformation erreicht werden kann, indem an jeden Eingabe- oder Ausgabeknoten eine Kante mit der Gewichtung angehängt wird . Die Art der Transformation, sagt Valiant kann durch Anhängen an Eingangs- oder Ausgangsknoten Ketten der Länge erreicht werden gewichtet mit und sind. $1^{st}$ $1$ $2^{nd}$ $2$ $x$ $y$

Ich konnte diese Aussagen nicht wirklich verstehen. Vielleicht sind sie bereits klar, aber ich kann immer noch nicht wirklich verstehen, warum das obige Konstrukt dazu beiträgt, realisierbare -Werte auf einer Basis mit der neuen Basis zu erreichen, die einer der oben genannten Typen ist. $valG$

Bitte helfen Sie mir, sie zu beleuchten. In einem anderen Sinne gibt es einige tensorfreie Umfragen für hologaphische Algorithmen, die online verfügbar sind. Die meisten von ihnen verwenden Tensoren, die mir leider Angst machen :-(

Beste -Akash

ds.algorithms counting-complexity survey Akash Kumar
quelle

Antworten:

Tensoren (in diesem Sinne) sind nur Anordnungen von Zahlen. Ich glaube, Sie werden keine tensorfreien Umfragen finden, es sei denn, sie sind völlig frei von Berechnungen.

Die Operation " " formalisiert sowohl die Operationen zum Ändern der Basis als auch zum Anhängen von Gadgets an jeden Ausgabeknoten (tatsächlich stelle ich mir eine Änderung der Basis gerne als eine Art Gadget-Operation vor). Sei ein Generator-Matchgate mit der Standardsignatur . Dies ist ein Array von Zahlen. Die Unterschrift auf neuer Basis erfolgt durch $T^{\otimes k}$ $\Gamma$ $M_{i_1i_2\cdots i_k}=u(\Gamma)$ $2^k$

$(T^{\otimes k}M)_{i_1i_2\cdots i_k}:=\sum_{i_1',\cdots,i_k'} T_{i_1i_1'} \cdots T_{i_ki_k'} M_{i_1'i_2'\cdots i_k'}$

wobei eine Zwei-mal-Zwei-Matrix ist, die die neue Basis beschreibt. $T$

Sei das Matchgate, das durch Hinzufügen von neuen Eckpunkten zu , wobei diese als neue Ausgänge betrachtet werden und sie durch eine Gewichtskante mit den alten Ausgängen verbunden werden . Dann ist die neue Signatur wobei die Matrix ist . Wenn Sie dann die Änderung der Basis durchführen Sie die Signatur erhalten . $\Gamma'$ $k$ $\Gamma$ $x$ $C^{\otimes k}M$ $C_{ij}$ $\begin{pmatrix}0&x\\1&0\end{pmatrix}$ $TC^{-1}$ $T^{\otimes k}M$

Colin McQuillan
quelle

S

$S$

u (Γ)

$u(\Gamma)$

S = S_{0}

$S = S_0$

T^{\otimes k} \times S = u (Γ)

$T^{\otimes k} \times S = u(\Gamma)$

v a l G (Γ, x)

$valG(\Gamma, x)$ Beispiel, dass er nur beabsichtigte, den perfMatch-Vektor als die Summe der Koeffizienten für die neue Basis auszudrücken. Ich kann mir jedoch nicht sicher sein, da ich offensichtlich keinen Hintergrund mit Tensoren habe.

Akash Kumar

C^{\otimes k} M

$C^{\otimes k}M$

S_{0}

$S_0$

(T^{- 1})^{\otimes k} S

$(T^{-1})^{\otimes k} S$

T

$T$

n_{0}, n_{1}, p_{0}, p_{1}

$n_0,n_1,p_0,p_1$

(0, 1, 1, 0, 1, 0, 0, 1)

$(0,1,1,0,1,0,0,1)$

x (1, 1, 1, 1 1, 1, 1, 0)

$x(1,1,1,1\ 1,1,1,0)$

C^{\otimes 3} w h e r e

$C^{\otimes 3} where$

C = (0, 1)^{t} (x = 1, 0)^{t}

$C = (0,\ 1)^t (x=1,\ 0)^t$

u (Γ)

$u(\Gamma)$

P_{3}

$P_3$

P_{3} ∖ Z

$P_3 \setminus Z$

u (P_{3}) = (0, 1, 0, 0, 1, 0, 0, 1)

$u(P_3)=(0,1,0,0,1,0,0,1)$

(1, 0, 0, 1, 0, 0, 1, 0)

$(1,0,0,1,0,0,1,0)$

(C^{\otimes 3} u (P_{3}))_{1, 2, 2} = 1

$(C^{\otimes 3} u(P_3))_{1,2,2}=1$