This post is a bit more abstract than the others, but important for a deeper understanding of quantum logic. Think of it as a course in a beautiful language that you have never before had the opportunity to speak.

Traditionally, mathematicians like to write down abstract definitions with a wide scope, while physicists need concrete examples to fit data. Quantum gravity blurs this distinction by constructing examples that are so incredibly special that they paradoxically give the mathematicians everything they want. To start with, let us look at the concept of geometric duality. This will work in any dimension, but is easiest to understand in dimension two.

Given a planar diagram built from points, edges and faces, there is a geometric dual which sends points to faces, faces to points, and edges to edges. For example, consider the black square lattice in the diagram. It’s points are the corners of the squares, and it’s square faces fill in the entire plane. The dual diagram is the blue square lattice, because every face on a black square is a blue point and every black edge is cut by one blue edge. In this case, both the black lattice and blue lattice happen to look the same, but this need not be the case.

Another example is the black lattice of triangles, also a tiling of the plane by one shape. It’s dual lattice is the hexagonal lattice.

How about three dimensions? Now points map to three dimensional pieces, faces to edges, and edges to faces. Once again, a cubic lattice has a dual identical cubic lattice. Another starting point is the body centered cubic (BCC) lattice, which is the combination of a cubic lattice and its dual. Dual to this lattice is a tiling of space by the permutohedron, shown below. This is the three dimensional analog of the hexagon. It’s coordinates (on a subspace in four dimensions) have been chosen to represent the group of permutations on four objects (given by the numbers 1,2,3 and 4).

Permutations are important because they act on finite sets, and classical mathematics is all about sets. But sets are themselves zero dimensional, in the sense that an element of a set is always an element (or object). Everything is on an equal footing, and even a subset of a set is a kind of element. A finite set is viewed as a collection of n points, and points are by definition zero dimensional.

Category theory is about the extension of sets to higher dimensional geometry, essential for quantum logic. Our first example is the one dimensional category of all finite sets, usually called Set. Every one dimensional category has both objects, which are zero dimensional, and edges, which are one dimensional. We put a direction on edges to make them arrows, because an edge usually represents an operation, like taking a function on a set and spitting out its values. Arrows between objects A and B can go in either direction. Different arrows can be composed if the ends match up. For instance, take a function f: A —> B and compose it with the function g: B —> C by doing ffirst and then g. The result is written gf: A —> C. Every object A comes with an identity arrow 1(A): A —> A which sends everything to itself.

Now you are only missing one little piece of the full technical definition: a one dimensional category is assumed to be associative, meaning that any three composable functions satisfy the rule (hg)f=h(gf). Different choices of bracket on objects ((AB)C or A(BC)) are usually represented by binary trees. In a category, there is no real equality between objects, because a set of apples is not the same thing as a set of oranges, even if they are both three point sets. In this case there may be a function, called an associator a, from one bracketed word to another.

The category Set is an example of a tensor category. This means that there is a composition on objects, as well as the composition on functions. In Set this is the Cartesian product of two sets, namely all possible ordered pairs made with one element from each set. Concretely, the product of the two sets {0,1} and {a,b} is the four element set {(0,a), (0,b), (1,a), (1,b)}.

We write the tensor product of A and B in a general category simply as AB (although this is non standard). Structure is imposed on a category by demanding certain properties for the arrows. For the tensor product, the important axiom is the MacLane pentagon, given below. Don’t worry about where it comes from. MacLane’s theorem says that the only rules we ever need for a tensor category are the pentagon and the unit laws.

On the pentagon, the points are the five possible ways to bracket four objects in a product. The blue binary trees encode the bracketing, when the leaves are labelled by A, B, C and D in that order. Each black edge is an associator arrow, which merely flips the bracket (AB)C to A(BC). The structure of the category includes such an associator a(ABC) for every triple of objects in the category. In Setwe can take these to be identity arrows, because brackets don’t matter for Cartesian products.

Now we need geometric duality. A tensor category is secretly a two dimensional gadget, because the tensor product makes objects into one dimensional arrows. The usual arrows are now two dimensional arrows, and there is only one hidden object. We mark two dimensional faces with bigger arrows. The black arrow diagram for the square of cis turned into a blue string diagram, as shown below. Because there is only one hidden object, there are no labels on black points, and no labels on the planar regions of the string diagram. The two grey arrows become two points on the blue diagram, where the strings cross. In many examples, the strings cross in the plane, but we are interested in including the third dimension, so we need another piece of structure: a braiding for the category. The third dimension means this: one hidden object in dimension zero and a second hidden object (an arrow) in dimension 1. In other words, by duality, the braided strings are really two dimensional arrows and the special points are three dimensional arrows.

So far we have tensor products and associators. The categories used in quantum computation are tensor categories with a braiding, plus a little more structure, making them ribbon categories. A good summary of the crucial axioms is given in Ross Street’s technical book on Quantum Groups.

A braiding for a tensor category is a collection of arrows c(AB): AB —> BA for every pair of objects A and B, represented by the single string crossing below. When objects are commutative, meaning that AB is essentially the same as BA, we don’t care how the strings cross, because doing ctwice will get us back where we started. But this is usually not the case.

Our physical categories are built with ribbons, or tangles of ribbons. Each piece of string is thickened into a ribbon, the corresponding structure being a set of twist maps t(A): A —> A for every object A. A piece of ribbon can be either flat or twisted, where one full twist represents the map t. We saw that twists are used to represent electric charge.

The proper twist map for more than one strand is not immediately obvious. On ribbons we want t(2) to look like this:

In general, we choose a category that encodes certain physical properties of interest, so the objects themselves might hide a great deal of structure. For a different problem, we might need a higher dimensional category that blows up the points into larger geometries. In particular, quantum mechanics uses linear spaces instead of sets, and we need the idea of a dual for objects. (The dual of a finite dimensional vector space is the set of all linear maps from the space into the underlying number field). This is easy to represent in the diagram: allow the ribbons to curl around in tangles of ribbons.

When a ribbon strand curls back up, it must go from a plus sign to a minus sign. It might also start and end at the bottom of the diagram. These tangle maps don’t need to preserve the number of points at the top and bottom. The dual of a set of signed points is the reversing of signs and the reversing of their order, so that up and down curls may be considered as structure maps.

Finally, a “braided tensor category with twists and duals on objects” is a suitable ribbon category for quantum computation. You are now a quantum gravity theorist!

What does any of this have to do with logic? In Set, the OR operation is a union of sets, and AND is intersection. In quantum mechanics, however, the OR operation cannot be the union of two subspaces, because such a union is not in general a subspace. Two distinct lines in a plane do not form a plane. OR is now the subspace of all linear combinations of these two lines, namely the plane in which they lie. For this reason, AND does not distribute over OR like it does for sets. Any hope we might have had of using classical logic is dashed. Luckily, classical logic is about the structure of the category Set, and for quantum logic we instead go to ribbon categories.