Algoritmos Holográficos - Equivalencia de Bases

Estaba revisando el trabajo seminal de Les Valiant y tuve un momento difícil con la Proposición 4.3 en la página 10 del documento.

No puedo ver por qué es el caso que si hay un generador con ciertos valores para con una base , entonces existe algún generador con el mismo valores para cualquier base $valG$ $\{(a_1,b_1) \ldots (a_r,b_r)\}$ $valG$ ( ) o ( ) para cualquier . $\{(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 señala la razón en el párrafo anterior: a saber, el tipo de transformación se puede lograr al agregar a cada nodo de entrada o salida un borde de peso . El tipo de transformación, Valiant dice, se puede lograr añadiendo a de entrada o salida nodos cadenas de longitud ponderados por y respectivamente. $1^{st}$ $1$ $2^{nd}$ $2$ $x$ $y$

Realmente no he podido entender estas declaraciones. Tal vez ya estén claros, pero aún así no puedo ver realmente por qué la construcción anterior ayuda a lograr valores de realizables con una base con la nueva base, que es uno de los tipos anteriores. $valG$

Por favor, ayuda a iluminarme. En una nota diferente, ¿hay algunas encuestas sin tensor para algoritmos holográficos disponibles en línea? La mayoría de ellos usan tensores que, lamentablemente, me asustan :-(

El mejor -Akash

ds.algorithms counting-complexity survey Akash Kumar
fuente

Respuestas:

Los tensores (en este sentido) son solo matrices de números, por lo que no creo que encuentres encuestas sin tensor a menos que estén completamente libres de cálculos.

La operación " " formaliza tanto las operaciones de cambio de base como la conexión de gadgets a cada nodo de salida (de hecho, me gusta pensar en un cambio de base como una especie de operación de gadget). Deje ser un matchgate generador con firma estándar . Esta es una matriz de números. La firma en una nueva base está dada por $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'}$

donde es una matriz de dos por dos que describe la nueva base. $T$

Deje sea el matchgate formado mediante la adición de nuevos vértices a , teniendo éstos a ser las nuevas salidas, y la conexión de ellos a los viejos salidas por un borde de peso . Entonces la nueva firma es donde es la matriz . Si a continuación, realizar el cambio de base se obtiene la firma . $\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
fuente

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)$ ejemplo que solo pretendía expresar el vector perfMatch como la suma de coeficientes wrt a la nueva base. Sin embargo, no puedo estar seguro de mi evidente falta de antecedentes con los tensores.

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$