10
$\begingroup$

I was going through Les Valiant's seminal paper and I had a tough time with Proposition 4.3 on page 10 of the paper.

I cannot see why is it the case that if there is a generator with certain values for $valG$ with a basis $\{(a_1,b_1) \ldots (a_r,b_r)\}$, then there exists some generator with same $valG$ values for any basis $\{(xa_1,yb_1) \ldots (xa_r,yb_r)\}$ ($1^{st} kind$) or $\{(xb_1,ya_1) \ldots (xb_r,ya_r) \}$ ($2^{nd} kind$) for any $x,y \in F$.

Valiant points out the reason in preceding paragraph - namely the $1^{st}$ kind of transformation can be achieved by appending to every input or output node an edge of weight $1$. The $2^{nd}$ kind of transformation, Valiant says, can be achieved by appending to input or output nodes chains of length $2$ weighted by $x$ and $y$ respectively.

I have not been really able to understand these statements. Maybe they are already clear, but still I cannot really see why the above construct helps achieve any realizable $valG$ values with one basis with the new basis which is one of the above types.

Please help illuminate them to me. On a different note, are there some tensor free surveys for hologaphic algorithms available online. Most of them use tensors which, sadly, scare me :-(

Best -Akash

Improve this question
$\endgroup$
8
$\begingroup$

Tensors (in this sense) are just arrays of numbers, so I don't think you'll find tensor free surveys unless they're completely free of calculations.

The "$T^{\otimes k}$" operation formalizes both the operations of changing basis and attaching gadgets to each output node (in fact I like to think of a change of basis as a sort of gadget operation). Let $\Gamma$ be a generator matchgate with standard signature $M_{i_1i_2\cdots i_k}=u(\Gamma)$. This an array of $2^k$ numbers. The signature in a new basis is given by

$(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'}$

where $T$ is some two-by-two matrix descring the new basis.

Let $\Gamma'$ be the matchgate formed by adding $k$ new vertices to $\Gamma$, taking these to be the new outputs, and connecting them to the old outputs by an edge of weight $x$. Then the new signature is $C^{\otimes k}M$ where $C_{ij}$ is the matrix $\begin{pmatrix}0&x\\1&0\end{pmatrix}$. If you then perform the change of basis $TC^{-1}$ you get the signature $T^{\otimes k}M$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Sorry for the late reply, I was occupied today. I am afraid, due to my limited understanding of tensors, I still cannot understand you. I used to think that the signature of a generator matchgate in the new basis, $S$ was derived from the signature $u(\Gamma)$ in the old basis by the solution $S = S_0$ to $T^{\otimes k} \times S = u(\Gamma)$. I thought Valiant mentioned in his $valG(\Gamma, x)$ example that he just intended to express perfMatch vector as the sum of coefficients wrt to the new basis. I cannot be sure though, for my obvious lack of background with tensors. $\endgroup$
    – Akash Kumar
    Feb 17 '11 at 4:06
  • $\begingroup$ [contd] Also, I am not able to follow your example with $C^{\otimes k}M$. Could you please elaborate a little more? Thanks -- Akash $\endgroup$
    – Akash Kumar
    Feb 17 '11 at 4:11
  • $\begingroup$ I'm happy to try to elaborate, but I might just be adding confusing notation. Could you answer this first: if you add edges at each output node, what effect do you think this would have on the signature? Also, that $S_0$ can be expressed as $(T^{-1})^{\otimes k} S$ - I can't remember off-hand what the actual coefficients of $T$ should be in terms of Valiant's $n_0,n_1,p_0,p_1$. $\endgroup$
    – Colin McQuillan
    Feb 17 '11 at 10:31
  • $\begingroup$ I will try to state my confusion with an example. Consider a generator which is path of length 3 where all the 3 nodes are o/p nodes. The std signature of this generator is $(0,1,1,0,1,0,0,1)$. And the signature of the modified gadget with 3 new nodes each connected to one o/p node in the std basis is $x(1,1,1,1\ 1,1,1,0)$. Could you please continue with this example? I would like to see how does $C^{\otimes 3} where $$C = (0,\ 1)^t (x=1,\ 0)^t$ act on $u(\Gamma)$. Thanks for your patience $\endgroup$
    – Akash Kumar
    Feb 17 '11 at 13:20
  • 1
    $\begingroup$ Let $P_3$ be a path of order 3. Call the vertices x,y,z where y is the middle vertex. $P_3 \setminus Z$ has a perfect matching iff Z is {x}, {z}, or {x,y,z}. So $u(P_3)=(0,1,0,0,1,0,0,1)$. With edges attached the signature is $(1,0,0,1,0,0,1,0)$. Try calculating for example $(C^{\otimes 3} u(P_3))_{1,2,2}=1$ using the formula above. $\endgroup$
    – Colin McQuillan
    Feb 17 '11 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.