Low Dimensional Topology

July 16, 2015

Boolean logic with braids

Filed under: Uncategorized — dmoskovich @ 3:03 am

First-off, I’m fairly chuffed that Tangle Machines (arXiv version HERE) was published in Proc. R Soc. A, and they even chose our figure for the cover! Computing with Coloured Tangles has also been accepted for publication. This is good.

One of the constructions of Tangle Machines, which I previously discussed HERE and HERE, is a universal set of logic gates using coloured tangles (and in fact we cheated, because our colouring wasn’t by a quandle but by a more general algebraic structure). It turns out that this idea isn’t new, and actually it’s been done better a long time ago in a different setting, and in a very nice way (thanks anonymous referee!). Boolean logic can be realized using coloured braids! And it’s even potentially useful in quantum computing! So today I’ll discuss this paper and the papers it references:

Alagic, G., Jeffery, S., and Jordan, S. Circuit Obfuscation Using Braids. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) (eds. S.T. Flammia and A.W. Harrow), Vol. 27, pp. 141–160.

We start with a group $G$ in which we choose two elements, one which we call zero’ and the other which we call one’. Our operation is conjugation $g \triangleright h = h^{-1}gh$. A computation is a braid coloured by elements of $G$, with strands incident to endpoints at the bottom $x_1, x_2,\ldots, x_k$ each of which is coloured by a zero or a one called the input of the computation, and strands incident to endpoints at the top $y_1, y_2,\ldots, y_l$ each of which is coloured by a zero or a one called the output of the computation. The braid may also have additional strands at the top and bottom (indeed it must if $k\neq l$). These extra strands, called ancilla, may be coloured by any element of $G$. The ancilla serve as catalysts for the computation and nothing more.

How does a braid compute? Moving up through the braid from bottom to top, we encounter braid group generators $\sigma_i$ describing strand $i$ crossing over strand $i+1$, and their inverses. If the colour of strand $i$ at the bottom of $\sigma_i$ is $h$ and the colour of strand $i+1$ at the bottom of $\sigma_i$ is $g$, then the colour of strand $i+1$ at the top is still $h$ while the colour of strand $i$ at the top is $g\triangleright h$.

What computations can a braid perform? A-priori, we might suspect that maybe it can’t do all that much, because conjugations are rather special operations. In particular, it doesn’t seem like we should be able to realize an AND gate with a braid. To remind you, $a\wedge b$, pronounces $a$ and $b$‘, returns $ab\bmod 2$. So it returns $1$ if both $a$ and $b$ are one, and zero otherwise. The reason AND seems really hard to realize using coloured braids (try it if you don’t believe me!) is that it responds differently to ones than to zeros, so there is an if’ concept built in; and how could a braid do that? More formally, it’s recovering a product from conjugation, which seems impossible.

It really looks like one should be able to prove that AND can’t be realized by braids, and this is what people indeed believed for a long time. This is one case in which our intuition is wrong, however. Kitaev showed that if the group $G$ is the symmetric group $S_5$, then AND can indeed be realized by a $G$-coloured braid (note: ancilla are important- this, and the fact that $A_5$ is `sufficiently rich’, is what comes to the rescue). The proof is pretty similar to a celebrated result of Barrington and of Krohn-Maurer-Rhodes about representing maps $G^n\rightarrow G$ using conjugations. Ogburn and Preskill showed that the alternating group $A_5$, which is half as large as $S_5$, is enough.

Monchon constructed a Toffoli gate braid, which is explicitly drawn in Appendix A of Alagic-Jeffery-Jordan. It has 132 crossings and 14 strands (11 of which are ancilla), so it isn’t an easy construction.

To remind the reader, a Toffoli gate is a universal reversible logic gate which contains within it a universal set of gates. Thus, an AND gate is a subcomputation of a Toffoli gate. A Toffoli gate accepts 3 bits $a$, $b$, and $c$, returns $a$ and $b$, and inverts $c$ if and only if $a=b=1$.

Explicitly, $(345)\in A_5$ encodes zero and $(435)\in A_5$ encodes one. You can see the construction there.

There are some obvious questions which this raises- as any binary boolean function can be realized by a coloured braid (this is what the above result shows), and because the boolean circuit model is Turing complete, we know that any computable function can be represented by an $A_5$-coloured braid with ancilla. It’s pretty clear, however, that it would be tremendously suboptimal to realize individual Toffoli gates and to string them all together- the braid language can recover boolean circuits, but not in a simple or intuitive way. How could a simple braid computation be performed? What is the simples braid that would realize some given binary boolean function, and how would we set-out to find it? Is the group $A_5$ the best possible, or are there more reasonable groups (in whatever sense) which do the same job?

How is all of this practical? Well, an element in the braid group can be thought of as a motion of points in a disc (more accurately, as an element of the fundamental group of a configuration space on the disc). The timelines of these moving points trace out the braid- for instance, if we have three points, one of which is stationary and two of which change places, we obtain $\sigma_1$ (or its inverse) in the braid group on 3 strands.

Now imagine 2-dimensional particles- anyons they are called, and they are just-about physical- which move around one another in a disc. Say they have 60 states, and when one moves around another it picks up a phase which corresponds to the conjugation operation. Again, this is just about physical. Then voilá! The above construction gives rise to a Toffoli gate $A_5$-coloured braid!

There’s more to the story. We can use braid relations, AKA Reidemeister moves on braids, to obfuscate or to disguise our computation for security purposes, so an eavedropper with access to the system would have trouble figuring out which computation was being performed.

Computing seems to have a definite topological side, which is only just now slowly emerging into the light. The visionary who first saw this was Kauffman. There are many sides to the story, and I’m sure that topology appears in many different and even independent ways; a Toffoli gate braid is a particularly pretty one.