Algorithmes holographiques - Équivalence des bases

Je parcourais le papier séminal de Les Valiant et j'ai eu du mal avec la proposition 4.3 à la page 10 du papier.

Je ne vois pas pourquoi est-ce que s'il y a un générateur avec certaines valeurs pour avec une base , alors il existe un générateur avec les mêmes valeurs pour tout base ( ) ou ( ) pour tout .{ ( a 1 , b 1 ) … ( a r , b r ) } v a l G { ( x a 1 , y b 1 ) … ( x a r , y b r ) } 1 s t k i n d { ( x b 1 , y $valG$$\{(a_1,b_1) \ldots (a_r,b_r)\}$$valG$$\{(xa_1,yb_1) \ldots (xa_r,yb_r)\}$$1^{st} kind$2 n d k i n d x , y ∈ $\{(xb_1,ya_1) \ldots (xb_r,ya_r) \}$$2^{nd} kind$$x,y \in F$

Valiant souligne la raison du paragraphe précédent - à savoir que le type de transformation peut être obtenu en ajoutant à chaque nœud d'entrée ou de sortie un bord de poids 1 . Le type de transformation 2 ^ {nd} , dit Valiant, peut être obtenu en ajoutant aux nœuds d'entrée ou de sortie des chaînes de longueur 2 pondérées respectivement par x et y . 1 2 n d 2 x $1^{st}$$1$$2^{nd}$$2$$x$$y$

Je n'ai pas vraiment pu comprendre ces déclarations. Peut-être qu'ils sont déjà clairs, mais je ne vois toujours pas vraiment pourquoi la construction ci-dessus aide à atteindre des valeurs valG réalisables $valG$avec une base avec la nouvelle base qui est l'un des types ci-dessus.

Aidez-moi à les éclairer. Sur une note différente, existe-t-il des enquêtes sans tensor pour les algorithmes holographiques disponibles en ligne. La plupart d'entre eux utilisent des tenseurs qui, malheureusement, me font peur :-(

Meilleur -Akash

Les tenseurs (dans ce sens) ne sont que des tableaux de nombres, donc je ne pense pas que vous trouverez des sondages sans tensor à moins qu'ils ne soient complètement libres de calculs.

L'opération " " formalise à la fois les opérations de changement de base et d'attachement de gadgets à chaque noeud de sortie (en fait j'aime penser à un changement de base comme une sorte d'opération de gadget). Soit un matchgate de générateur avec la signature standard . C'est un tableau de nombres. La signature dans une nouvelle base est donnée par Γ M i 1 i 2 ⋯ i k = u ( Γ ) 2 $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'}$

où est une matrice deux par deux décrivant la nouvelle base.$T$

Soit la porte de correspondance formée en ajoutant nouveaux sommets à , en les prenant comme nouvelles sorties et en les connectant aux anciennes sorties par un bord de poids . La nouvelle signature est alors où est la matrice . Si vous effectuez ensuite le changement de base vous obtenez la signature . k Γ x C ⊗ k M C i j ( 0 x 1 0 ) T C - 1 T ⊗ k$\Gamma'$$k$$\Gamma$$x$$C^{\otimes k}M$$C_{ij}$$\begin{pmatrix}0&x\\1&0\end{pmatrix}$$TC^{-1}$$T^{\otimes k}M$