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.

2 Comments »

  1. Congratulations, very interesting! Egotistically, I noticed some typos in the references. The GLC actors arXiv:1312.4333 is different from Chemlambda, universality and self-multiplication, arXiv:1403.8046, which was published in the ALIFE 14.
    Just for fun, not Toffoli but the equivalent Fredkin gate in chemlambda here.

    Comment by chorasimilarity — July 16, 2015 @ 5:51 am | Reply

    • This is very nice- just the kind of thing it’s fantastic to see that chemlambda can do!
      Sorry for the error- it’s too late to correct in the published version, but if we put up a new ArXiv version then we’ll try to catch it there.

      Comment by dmoskovich — July 17, 2015 @ 7:12 am | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: