Голографические алгоритмы - эквивалентность основ

Я просматривал оригинальную статью Les Valiant, и мне было тяжело с предложением 4.3 на странице 10 статьи.

Я не могу понять, почему это так, что если существует генератор с определенными значениями для с базисом , то существует некоторый генератор с таким же значения для любого базиса $valG$ $\{(a_1,b_1) \ldots (a_r,b_r)\}$ $valG$ ( ) или ( ) для любого . $\{(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$

Доблестные указывает на причину в предыдущем параграфе , а именно - в вид преобразования может быть достигнуто путем добавления к каждому входу или выходу узла края веса . вид трансформации, Валиант говорит, может быть достигнуто путем добавления к входным или выходным узлами цепи длиной , взвешенных по и соответственно. $1^{st}$ $1$ $2^{nd}$ $2$ $x$ $y$

Я не был в состоянии понять эти заявления. Возможно, они уже понятны, но все же я не могу понять, почему приведенная выше конструкция помогает достигать любых реализуемых значений на одной основе с новой базой, которая является одним из вышеуказанных типов. $valG$

Пожалуйста, помогите осветить их мне. С другой стороны, есть ли некоторые тензорные обзоры голографических алгоритмов, доступные онлайн. Большинство из них используют тензоры, которые, к сожалению, пугают меня :-(

Бест -Акаш

ds.algorithms counting-complexity survey Акаш Кумар
источник

Ответы:

Тензорные (в этом смысле) - просто массивы чисел, поэтому я не думаю, что вы найдете обзоры без тензорных вычислений, если они не полностью свободны от вычислений.

Операция « » формализует как операции изменения базы, так и присоединения гаджетов к каждому выходному узлу (на самом деле мне нравится думать об изменении базы как своего рода операция гаджета). Пусть - это спичечная точка генератора со стандартной сигнатурой . Это массив из чисел. Подпись в новой основе дается $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'}$

где - некоторая матрица два на два, описывающая новый базис. $T$

$\Gamma'$ $k$ $\Gamma$ $x$ $C^{\otimes k}M$ $C_{ij}$ $\begin{pmatrix}0&x\\1&0\end{pmatrix}$ $TC^{-1}$ $T^{\otimes k}M$

Колин Маккуиллан
источник

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)$ Например, он просто намеревался выразить вектор perfMatch как сумму коэффициентов относительно нового базиса. Я не могу быть уверен, хотя, из-за моего очевидного отсутствия фона с тензорами.

Акаш Кумар

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$