Holographic Algorithms Part 4: Clifford Algebras and Spinors

Recall that two posts ago, I mentioned that Landsberg et al. observed that the matchgate identities are merely the defining equations of the spinor varieties. In this post, I will make explore what this really means in the hopes of describing to the reader their vision of the beautiful geometric reasons why holographic algorithms work. The big picture is that holographic algorithms are all about the efficient computation of some custom-made Holant that captures the answer to the combinatorial problem at hand. We come up with this exponentially large vector pairing (i.e. tensor contraction) and magically manage to compute it in polynomial time basically by computing a determinant. When do such efficiently computable pairings occur in geometry? Well if you take vectors in the cones of ${G(k,V)}$ and ${G(k,V^*)}$ (informally, vectors close enough to a ${k}$ -plane that they can be regarded as decomposable in ${\Lambda^kV}$ or ${\Lambda^kV^*}$ respectively) they turn out to be vectors consisting of determinants of minors of some matrix, and their pairing is merely the determinant of a related matrix. As it will turn out, if you take points in the variety of pure of spinors, they can likewise be characterized as vectors of “sub-Pfaffians” of some matrix, and a pairing between two such vectors is merely the Pfaffian of a related matrix. These are the kinds of efficiently computable pairings holographic algorithms take advantage of.

But it’s not enough to know that there exist special vectors whose pairings are easy to compute. After all, as a stupid example, the pairing between two ${2^n}$ -vectors supported in only ${\text{poly}(n)}$ dimensions is also computable in ${\text{poly}(n)}$ time. What distinguishes the vectors that feature in holographic algorithms from these vectors is the surprising availability of the former in complexity theory problems. Whereas there are way too many vectors in ${\mathbb{C}^{2^n}}$ not supported on only polynomially many dimensions, the codimensions of ${G(k,V)}$ for ${V}$ of low dimension and the spinor variety over low dimensions are quite small, and just as we’ve seen with matchgates, the vector spaces involved can often be decomposed into small enough “local” components (this local decomposition is key, because the abovementioned codimensions blow up very quickly).

In what follows, I hope to give a rigorous treatment of these ideas. My main references Chevalley’s The Algebraic Theory of Spinors and Clifford Algebras and the fifth chapter of Varadarajan’s lecture notes on supersymmetry for the development of the basic theory of Clifford algebras and spinors, and Landsberg’s Tensors: Geometry and Applications and Manivel’s On Spinor Varieties and Their Secants for establishing the connection between the matchgate identities and the variety of pure spinors. As always, if there are any mistakes in presentation below, they are entirely my fault.

1. Clifford Algebras and Spinors

“No one fully understands spinors. Their algebra is formally understood but their general significance is mysterious. In some sense they describe the “square root” of geometry and, just as understanding the square root of −1 took centuries, the same might be true of spinors.” -Michael Atiyah

As a remark, I make no attempt to cover technical material related to spinors and Clifford algebras beyond the scope of their relevance to holographic algorithms, so I apologize for failing to include certain key ideas (e.g. anything more than a basic mention of the graded structure of the Clifford algebra).

The notion of a spinor, while not named at the time, first came up in Cartan’s famous classification of the simple representations of all simple Lie algebras when he discovered an “exotic” representation of ${\mathfrak{so}(n)}$ not obtainable from tensors over the defining representation (the reason being that the weights of representations obtained from the usual tensor constructions are integral while those of the spin representation are odd multiples of 1/2). We see the spin representation come up immediately, for example, from the fact that ${\mathfrak{so}(3)\simeq\mathfrak{su}(2)}$ (the belt trick): the spin representation is merely the faithful representation of degree 2 of ${\mathfrak{su}(2)}$ . Spinors are just the vectors acted on by the spin representation.

In any case, the cleanest route to developing these notions will be from the point of view of Clifford algebras, which can be thought of in one way as providing a generalization of the multiplicative structure of the vector spaces of complex numbers, quaternions, and octonions to higher dimensions. In our discussion below, we will for convenience restrict ourselves to the field ${k = \mathbb{R}}$ , though the results are valid over all fields of characteristic not equal to 2. Let ${M}$ denote a real vector space of dimension ${n}$ , let ${Q}$ be some quadratic form, and let ${B}$ denote the symmetric bilinear form associated with ${Q}$ (namely, ${B(x,y) = Q(x+y)-Q(x)-Q(y)}$ ).

The Clifford algebra ${C = C(M)}$ of ${M}$ associated to ${Q}$ is defined to be the ${k}$ -algebra ${T(M)/I}$ , where ${I}$ is the ideal in ${T}$ generated by all elements of the form ${x\otimes x - Q(x)}$ .

${T(M)}$ is graded, so denote by ${T_+(M)}$ and ${T_-(M)}$ the direct sums of the respectively even and odd components of ${T(M)}$ , and denote by ${C_+(M)}$ and ${C_-(M)}$ the spaces ${T_+(M)/(T_+(M)\cap I)}$ .

As a first observation, note that there is a natural map ${M\rightarrow C(M)}$ , and it’s easy to see that in fact this natural map is an injection; so we’ll regard ${M}$ as sitting inside ${C(M)}$ . Now let’s prove some results on the structure of ${C(M)}$ which will allow us to define spin representations.

As a second observation, we can characterize ${C(M)}$ in terms of the exterior algebra of ${M}$ :

The underlying vector space of ${C(M)}$ is isomorphic to ${\Lambda M}$ .

Proof: There is a natural filtration ${T_0\subseteq T_1\subseteq\cdots}$ corresponding to ${T(M)}$ , and projecting this filtration down to ${C(M)}$ gives a filtration ${C_0\subseteq C_1\subseteq\cdots}$ on ${C(M)}$ . But the graded ring ${R}$ associated to this filtration is isomorphic to ${\Lambda(V)}$ . Indeed, ${R_1 = M}$ , and for any ${v\in M}$ , ${v^2 = Q(v)\in C_0}$ , from which we conclude that we have a natural isomorphism of graded algebras ${R\rightarrow \Lambda(V)}$ . But as vector spaces, ${R}$ and ${C(M)}$ are isomorphic, so we’re done. $\Box$

As a third observation, real Clifford algebras are parametrized quite nicely. By Sylvester’s law of intertia, quadratic forms can be diagonalized into the form ${Q(x) := x^2_1+\cdots+x^2_p - x^2_{p+1}-\cdots - x^2_{q}}$ for some ${p,q}$ which are invariants of ${Q}$ , so the real Clifford algebras are parametrized by these invariants. We will thus denote them by ${C^{p,q}}$ when we wish, in which case if ${Q(x) = \sum_i \epsilon_i x^2_i}$ , we can choose generators ${e_1,...,e_n}$ of ${C^{p,q}}$ satisfying ${e^2_i = \epsilon_i}$ and ${e_ie_j + e_je_i = 0}$ .

If ${n}$ is even, then ${C(M)}$ is a central simple algebra.

Proof: Say that ${C(M) = C^{p,q}}$ for ${p<q}$ , and pick the generators ${e_1,...,e_n}$ described above, but assume that we’ve diagonalized ${Q}$ so that ${\epsilon_{n-1}\neq\epsilon_n}$ . Then note that the elements ${f_1 = e_1\cdots e_{n-1}}$ and ${f_2 = e_1\cdots e_{n-2}e_n}$ satisfy ${f_1f_2 + f_2f_1 = 0}$ and ${f^2_1 = -f^2_2}$ and thus generate ${C^{1,1}}$ , which is the ${2\times 2}$ real matrix algebra ${M(2)}$ , while ${e_1,...,e_{n-2}}$ generate ${C^{p-1,q-1}}$ . The conclusion is that ${C_{p,q} = C_{p-1,q-1}\otimes M(2) = C_{0,q-p}\otimes M(2^p)}$ , and it remains to show that ${C_{0,q-p}}$ is central simple. For those familiar with the proof of Bott periodicity with Clifford algebras, it is easy to check using this same ${f_1}$ , ${f_2}$ trick that while the ${f_1}$ and ${f_2}$ don’t consistently generate the same algebra ${M(2)}$ , the intermediate algebras generated at each step tensor together nicely, so that for all ${m}$ , we get ${C_{0,2m+8} = C_{0,2n}\otimes M(16)}$ , and we’re done. $\Box$

While we cannot make the same claim for ${n}$ odd, we can make this claim about ${C_+(M)}$ :

If ${n}$ is odd, then ${C_+(M)}$ is a central simple algebra.

Proof: ${C_+(M)}$ is generated by ${g_2 = e_1e_2,...,g_{n-1} = e_1e_{n-1}}$ , which satisfy ${g_ig_j + g_jg_i = 0}$ and ${g^2_i = -\epsilon_1\epsilon_i}$ so that ${C_+(M)}$ is isomorphic to just ${C_{p,q-1}}$ or ${C_{q,p-1}}$ , which we know from the previous discussion to be central simple. $\Box$

Now let ${G}$ denote the orthogonal group of transformations preserving ${B}$ .

The Clifford group ${\Gamma}$ of ${G}$ is the set of ${s\in C(M)}$ for which conjugation of any ${x\in M}$ gives something inside ${M}$ . Let ${\chi}$ be the linear representation of ${\Gamma}$ sending ${s}$ to this conjugation map; call this the vector representation of ${\Gamma}$ .

In fact, ${\chi}$ sends ${\Gamma}$ not just into ${\text{End}(C(M))}$ but into ${G}$ : ${Q(sxs^{-1}) = (sxs^{-1})^2 = sx^2s^{-1} = Q(x)}$ . Moreover, it is known that if the rank of ${Q}$ is even (resp. odd), ${\chi(\Gamma)}$ is all of ${G}$ (resp. the even-graded elements of ${G}$ with determinant one), though we’ll omit this proof.

Moving onto the spin representation, assume first that ${n}$ is even. We know ${C(M)}$ is simple, and simple representations of simple algebras are equivalent, so pick any such representation, and this is the spin representation. Vectors in the space over which it acts are called spinors.

On the other hand, assume that ${n}$ is odd. We can no longer say that ${C(M)}$ is simple, but we do know that ${C_+(M)}$ is, so again, all simple representations of this are equivalent. By Lemma 1 below, there are two ways to extend this unique spin representation of ${C_+(M)}$ to a representation, and these are the spin representations of ${C}$ , with their corresponding spinors defined as above.

If ${C(M)}$ is not simple, there are exactly two ways to extend the spin representation ${\rho^+}$ on ${C_+(M)}$ to one on ${C}$ .

Proof: Before we jump to the proof of this, let’s prove a basic but key fact about the center ${Z}$ of ${C(M)}$ :

Claim 1: If ${V}$ is of odd dimension, then ${Z = k[\epsilon]}$ for some odd element ${\epsilon}$ for which ${\epsilon^2 = 1}$ .

Proof: For orthogonal basis ${\{e_0,...,e_n\}}$ , we will denote ${e_I = \prod_{i\in I}e_i}$ . If ${i\in I}$ , then ${e_Ie_i = (-1)^{|I|+1}e_ie_I}$ ; otherwise ${e_Ie_i = (-1)^{|I|}e_ie_I}$ . Pick ${x}$ in the center, and write it as ${\sum_I a_Ie_I}$ . Then one can check that ${xe_j = e_jx}$ for all ${j}$ implies that ${a_I = 0}$ for all ${I}$ except ${I = \{0,...,2m\}}$ , and ${\prod^{2m}_{i=0}e_i}$ is the odd element ${\epsilon}$ that we’re looking for, up to scaling. $\Box$

Now write any ${x\in C(M)}$ uniquely as ${x_1 + x_2\epsilon}$ for ${x_1,x_2\in C_+(M)}$ . The maps ${x\mapsto x_1 + x_2}$ and ${x\mapsto x_1 - x_2}$ are homomorphisms ${\phi_1,\phi_2: C(M)\rightarrow C_+(M)}$ . Now simply compose the spin representations with these ${\phi_1}$ and ${\phi_2}$ to obtain two distinct representations ${\rho_1}$ and ${\rho_2}$ .

Now say that we had another representation of ${C(M)}$ extending ${\rho^+}$ . Call it ${\rho'}$ , and say that ${\rho'(z) = \sigma}$ . The space ${S}$ of spinors decomposes into ${S_1}$ , those ${w}$ for which ${\sigma w = w}$ , and ${S_2}$ , those ${w}$ for which ${\sigma w = -w}$ . But ${\rho^+(x)}$ preserves the action of both of these subspaces, and by the fact that ${\rho^+}$ is simple, we conclude that ${A}$ must be either ${S_1}$ or ${S_2}$ . $\Box$

2. Pure Spinors

The particular kinds of spinors which form the bridge between geometry and holographic algebras are the so-called “pure spinors.” We begin by exploring these in the classical sense. The intuition is that pure spinors corresponding to a certain kind of subspace of ${M}$ are the analogue of “decomposable vectors” associated to a subspace of ${M}$ . They’re particularly nice because they correspond to maximal linear subvarieties of the quadric ${Q = 0}$ .

Before we can define pure spinors, here is the key preliminary result. For simplicity, we will assume that ${M}$ is of even dimension. Pick a splitting into maximal isotropic spaces ${N + P}$ . Denote the uniquely defined spin representation of ${M}$ by ${\rho}$ .

The intersection between a minimal left ideal ${\mathfrak{a}}$ and a minimal right ideal ${\mathfrak{b}}$ of ${C(M)}$ is a 1-dimensional vector space.

Proof: A theorem due to Brauer tells us that ${\mathfrak{a} = C(M)e}$ and ${\mathfrak{b} = e'C(M)}$ for some idempotents ${e}$ and ${e'}$ .

If ${H}$ is the kernel of ${\rho(e)}$ and ${H'}$ is the image of ${S}$ under the projection ${\rho(e)}$ , then we see first off that for all ${x\in C(M)}$ , ${\rho(xe)}$ maps ${H}$ to zero. On the other hand, for any ${v}$ that maps ${H}$ to zero, ${v = ve}$ ( ${e}$ acts as the identity on ${H'}$ ), from which we conclude that ${\mathfrak{a}}$ is the set of elements in ${C(M)}$ that kill ${H}$ . But the set of elements in ${C(M)}$ that kill any ${H_1}$ bigger than ${H}$ likewise corresponds to a left ideal smaller than ${\mathfrak{a}}$ , contradicting minimality. We conclude that ${H}$ is a hyperplane.

The argument for ${\mathfrak{b}}$ is analogous. If ${D'}$ is the image of ${S}$ under the projection ${\rho(e')}$ , then we see first off that for all ${x\in C(M)}$ , ${\rho(e'x)}$ sends ${D'}$ to itself. On the other hand, for any ${v\in C(M)}$ that does this, ${v = e'v}$ ( ${e'}$ acts as the identity on ${D'}$ ). The set of elements of ${C(M)}$ that project ${S}$ into a ${D'_1}$ smaller than ${D'}$ corresponds to a right ideal smaller than ${\mathfrak{b}}$ , contradicting minimality. We conclude that ${D'}$ is a line.

${\mathfrak{a}\cap\mathfrak{b}}$ is thus the set of ${v\in C(M)}$ which kill ${H}$ and project ${S}$ into ${D_1}$ . For ${x\not\in H}$ , ${\rho(v)x}$ lies in a line. If we pick a basis element ${y}$ for ${D'}$ , ${v}$ is determined exactly by the ${a}$ for which ${\rho(v)x = ay}$ , so we conclude that ${\mathfrak{a}\cap\mathfrak{b}}$ is of dimension 1. $\Box$

Now take ${Z}$ to be a maximal isotropic subspace of ${M}$ . and say ${Z}$ generates ${C^Z}$ as a subalgebra of ${C(M)}$ . Pick a basis ${\{z_1,...,z_r\}}$ of ${Z}$ and define ${f_Z}$ to be ${\prod^r_{i=1}z_i}$ . Also define ${f}$ to be ${\prod^r_{i=1}f_i}$ for basis elements ${f_i}$ of ${P}$ . By Lemma 1, we note that both ${f}$ and ${f_Z}$ is defined up to a multiplicative factor, independent of the choice of bases. But one can show that ${C(M)f}$ and ${f_ZC(M)}$ are minimal left and right ideals respectively.

Now because ${Cf}$ and ${f_ZC}$ intersect on a line, say that their intersection is some ${S_Zf}$ for one-dimensional subspace ${S_Z}$ . ${S_Z}$ is called the line of representative spinors of ${Z}$ .

A pure spinor is any spinors representative of some maximal isotropic ${Z}$ .

These spinors are called “representative” for the following reason:

If ${u_Z}$ is a representative spinor of ${Z}$ , then ${Z}$ is precisely the set of all ${x\in M}$ which kill ${u_Z}$ .

Proof: Recall that for ${M}$ of even dimension, ${\chi(\Gamma) = G}$ , meaning there must exist some ${s\in\Gamma}$ by which ${P}$ can be conjugated to obtain ${Z}$ . As such, we’ll assume that ${Z = P}$ , in which case the corresponding line of pure spinors contains ${u_Z = 1}$ . But ${\rho(x)}$ for any ${x}$ is multiplication by the component of ${x}$ inside ${N}$ , and this map is zero iff this component is zero, i.e iff ${x\in P = Z}$ . $\Box$

There is thus a correspondence between maximal isotropic subspaces of ${V}$ and lines of pure spinors. As such, we’ll define the so-called spinor variety as the variety of all maximal isotropic subspaces of ${V}$ .

This variety consists of two connected components ${S_+}$ and ${S_-}$ such that two maximal isotropic subspaces lie in the same component iff their intersection has dimension of the same parity as ${n}$ .

As an aside, recall that one of the ingredients for holographic algorithms to work is that “efficient pairings can be computed quite often.” Once we establish the connection between standard signatures and points on the spinor variety, this statement translates to the fact that “the spinor varieties over low dimensions have low codimension.” Indeed, the spinor varieties over dimensions 2, 3, and 4 are ${\mathbb{P}^1\sqcup\mathbb{P}^1\subset\mathbb{P}^2}$ , ${\mathbb{P}^3\subset\mathbb{P}^3}$ , and ${Q^6\subset\mathbb{P}^7}$ .

3. Sub-Pfaffians and Matchgates Revisited

Having developed the foundations for the theory of spinors, we will now show how they relate to the matchgate identities. In this section, we will eventually characterize points on the spinor variety in terms of sub-Pfaffians.

Before we do this however, let’s look at the analogous correspondence in the case of the Grassmannian manifold ${G(k,M)}$ .

The Plucker embedding sends ${G(k,M)}$ to the projectivization of ${\mathbb{P}(\Lambda^k M)}$ via ${\{e_1,...,e_k\}\mapsto[e_1\hat\cdots\hat e_k\}}$ so that the cone of the Grassmannian is the set of decomposable vectors inside ${\Lambda^k M}$ .

Write ${M}$ as ${E\oplus F}$ for ${k}$ -plane ${E}$ . Say that ${E}$ has basis elements ${e_1,...,e_k}$ and ${F}$ has basis elements ${f_1,...,f_{n-k}}$ . The neighbors of ${E = [v(0)]}$ , can be locally parametrized by matrices ${\{x^i_j\}}$ of coordinates of ${E^*\otimes F}$ (i.e. the tangent space at the point ${E}$ of ${G(k,M)}$ ) as ${[v(x^i_j)] = \left[(e_1 + \sum_i x^i_1f_i)\hat\cdots\hat(e_k + \sum_i x^i_k f_i)\right]\in\mathbb{P}\Lambda^k M}$ . Then one can check that for ${I\subset [k]}$ and ${J\subset [n-k]}$ of the same size, the coordinate of the ${(I,J)}$ th basis element ${b_1\hat\cdots b_k}$ where ${b_i = e_i}$ for ${i\in I\subset [k]}$ and ${b_i = f_{J_i}}$ otherwise equals the determinant of ${(x^i_j)}$ with rows indexed by ${I}$ and columns indexed by ${J}$ .

The relationship between the spinor variety and sub-Pfaffians of some coordinate matrix is completely analogous. But first, we give a slightly different, cleaner formulation of spinors as sub-Pfaffians using an exponential map. Pick a basis ${\{e_1,...,e_r\}}$ of ${N}$ . If ${u = \sum_{i<j}a_{ij}e_ie_j}$ , define ${\exp(u) = \prod_{i<j}(1+a_{ij}e_ie_j)}$ . This map has all the properties one would expect of an exponential map: 1) ${\exp(u+u') = \exp(u)\exp(u')}$ , 2) it is approximated by ${1+u}$ in the sense that if ${u}$ is the multiple of any basis element or in fact anything decomposable, then ${\exp(u) = 1+u}$ , and ${\exp(-u) = (\exp(u))^{-1}}$ . Furthermore, one can check that conjugation by any individual factor ${(1+e_ie_j)}$ preserves ${M}$ , so ${\exp(u)}$ is always in ${\Gamma}$ , and furthermore ${\rho(\exp(u))}$ is just multiplication by ${\exp(u)}$ . The reason we introduce this map is that the coefficients of ${e_{i_1}\cdots e_{i_k}}$ for all ${k}$ are precisely the Pfaffian of the submatrix of ${(a_{ij})}$ with rows and columns indexed by the ${i_1,...,i_k}$ .

The main result of this section is the following characterization due to Chevalley of all pure spinors:

A spinor is pure iff it can be represented as ${c\cdot\exp(u)e_1\cdots e_k}$ for some linearly independent ${e_1,....,e_k}$ in ${N}$ and scalar ${c\in k}$ . If ${u}$ represents ${Z}$ , ${e_1,...,e_k}$ are a basis of ${Z\cap N}$ .

Proof: To prove this, we’ll need two auxiliary results.

Let ${A}$ be the space spanned by ${e_1,...,e_k}$ , and let ${A'}$ be the ${P}$ -component of ${A}$ ‘s conjugate. Then ${A + A'}$ is a maximal isotropic subspace, and ${e_1\cdots e_k}$ represents ${A + A'}$ .

If ${Z,Z'}$ are all maximal isotropic subspaces, and ${Z\cap N = Z'\cap N}$ , then there exists a ${u = \sum_{i<j} a_{ij}e_ie_j}$ for which ${\chi(\exp(u))}$ sends ${Z}$ to ${Z'}$ and fixes every point of ${N}$ .

Let’s first see how these two lemmas prove Theorem 3. We know that ${x_1\cdot x_h}$ represents a space ${Z}$ whose ${N}$ -component has basis ${x_1\cdots x_h}$ . By our characterization of the space that a pure spinor represents as the space of all things killing it, the space that ${c\cdot\exp(u)e_1\cdots e_k}$ represents is ${Z}$ conjugated by ${\exp(u)}$ . But ${\chi(\exp(u))(Z)\cap N = Z\cap N}$ because the elements of ${N}$ are fixed by conjugation by ${\exp(u)}$ , so we also get the second part of the theorem.

In the other direction, start with any maximal isotropic ${Z'}$ . Take ${Z}$ , ${Z'}$ , and ${Z''}$ in the second lemma to be ${N}$ , ${Z}$ , and ${Z'}$ as defined above. As we’ve already noted, ${e_1\cdots e_k}$ represents ${Z}$ , and by the second lemma we have some ${u}$ for which ${\chi(\exp(u))}$ sends ${Z}$ to ${Z'}$ , so the line of representative spinors consists of multiples of ${\exp(u)e_1\cdots e_k}$ , as desired.

It remains to prove our lemmas. For the first lemma, ${A}$ and ${A'}$ clearly have dimensions which sum to that of ${N}$ , and the bilinear form ${B}$ associated to ${C(M)}$ is nondegerate, so ${A + A'}$ , which is clearly isotropic, is maximal. ${e_1\cdots e_k}$ represents it because ${A+A'}$ is the space of all elements killing it.

For the second lemma, we will show that any map in the orthogonal group ${G}$ fixing the points of ${N}$ is of the form ${\chi(\exp(u))}$ for some ${u}$ . After that, it suffices to construct a map sending ${Z'}$ to ${Z''}$ while fixing ${Z}$ .

Start with any ${\sigma\in G}$ fixing points in ${N}$ . It turns out that it’s possible to construct bases for ${N}$ and ${P}$ , call them ${\{x_1,...,x_{n/2}\}}$ and ${\{y_1,...,y_{n/2}\}}$ , such that ${B(x_i,y_j) = \delta_{ij}}$ , ${\sigma(y_i) = y_i}$ for all ${i > 2m}$ for some ${m}$ , and ${\sigma(y_j) = \sigma(y_j)\pm x_{j-1}}$ for all ${j\le m}$ , where the ${\pm}$ depends on the parity of ${j}$ . The ${u}$ we are looking for is then simply ${u = x_1x_2 + \cdots + x_{2m-1}x_{2m}}$ .

Finally, to construct the desired map sending ${Z}$ to ${Z'}$ , define ${P_1}$ to be the subspace of ${P}$ spanned by ${y_1,...,y_k}$ , and ${Z''}$ to be ${(Z\cap N) + P_1}$ . It suffices to show that ${Z}$ and ${Z''}$ can both be sent to ${Z''}$ while fixing points of ${N}$ . We will omit the details, but the map from ${Z}$ to ${Z''}$ sends ${Z\cap N}$ via the identity and ${Z\backslash(Z\cap N)}$ via taking the ${P}$ -component. $\Box$

The big conclusion is that the the matchgate identities cut out the variety of pure spinors!

Anyways, for the sake of concreteness and completeness, let’s continue the analogy we started with. Instead of a point on ${G(k,M)}$ , consider a point on the spinor variety of ${M}$ . In other words, rather than a ${k}$ -plane ${E}$ , let’s take a maximal isotropic subspace ${E}$ , and let ${M = E\oplus F}$ as before. Whereas the Plucker map embeds ${G(k,M)}$ into the projectivization of ${\Lambda^k M}$ , our discussion of the spinor variety tells us we have an embedding of ${S_{\pm}}$ the projectivization of ${\Lambda^{\pm}M}$ (where ${\Lambda^+}$ denotes the sum of the even graded components of ${\Lambda M}$ and ${\Lambda^-}$ denotes the sum of the odd ones). Whereas the neighbors of a ${k}$ -plane in ${G(k,M)}$ were parametrized by any matrix of coordinates inside ${E^*\otimes F}$ , as one can check, the neighbors of a maximal isotropic subspace in the spinor variety are parametrized by skew-symmetric matrices ${x^i_j}$ :

The space ${E(x^i_j)}$ generated by ${e_1 + \sum_i x^i_1f_i,...,e_k + \sum_i x^i_kf_k}$ is maximal isotropic iff ${(x^i_j)}$ is skew-symmetric.

Whereas the decomposable vector ${[v(x^i_j)]}$ in ${\Lambda E}$ had coordinates the determinants of submatrices of ${(x^i_j)}$ , the pure spinor corresponding to ${E(x^i_j)}$ , by Chevalley’s result, has coordinates the Pfaffians of certain submatrices of ${(x^i_j)}$ . Specifically, a bit of computation gives us the following observation.

For ${I}$ even, the ${([k]\backslash I)}$ th coordinate of this pure spinor is the Pfaffian of the submatrix of ${(x^i_j)}$ with rows and columns indexed by ${I}$ .

4. Conclusion

In this post, we began with a classical presentation of the matchgate identities and proceeded to develop the appropriate theory for understanding where these identities really come from. To reiterate, this latter discussion in some sense “demystifies” holographic algorithms by uncovering the underlying geometric reason why holographic algorithms work: realizable signatures of arity ${n}$ are parametrized by points on the variety of pure spinors over dimension ${n}$ , tensor contractions are often easy when there is this kind of additional structure because, and for low ${n}$ such varieties have low codimension so that this happens nontrivially often.

Of course, the bigger question is still whether holographic algorithms could ever be used to give a proof that ${P = NP}$ (in fact, such a proof would actually imply the more astounding result that ${NC^2 = \#P}$ ), and if not, how geometry could somehow “know” that certain problems are intractable.

I don’t know if anyone has a convincing answer yet. To further explore the full potential of holographic algorithms, I will take a detour from these more theoretical considerations in the next post and cover some more of Cai’s work, namely his recent work on holographic algorithms over domains of larger size than just the Boolean domain, asking whether larger domains, unlike larger bases, can add power to holographic algorithms.

for formal reasons

math/cs writings

Holographic Algorithms Part 4: Clifford Algebras and Spinors

Leave a comment Cancel reply

Share this:

Related

Leave a comment Cancel reply