The article Zipper logic arXiv:1405.6095 contains in its last section a discussion about the role of topology in computing formalisms which use topological objects, like tangle diagrams, or other graphs, and graph rewrites.

The purpose of this post is to start a discussion about the differences between two uses of graph rewrites in such formalisms.

I shall use further the NTC vs TC denomination suggested by Louis Kauffman instead of the longer one:

- NTC = “topology does not compute” , meaning that the graph rewrites are NOT part of the computation notion
- TC = “topology computes”, meaning that the graph rewrites are the fundamental blocks of the computation notion.

There are many articles which fall in the NTC camp, among them the ZX calculus of Coecke and Duncan from Interacting Quantum Observables: Categorical Algebra and Diagrammatics arXiv:0906.4725 [quant-ph] , which is a part of the beautiful Categorical Quantum Mechanics. I shall use this article as an anchor which allows to compare with the TC camp. In future posts I shall add more articles to the list, because this is a rather big research field now.

Chemlambda is in the TC camp, like zipper logic.

So let us compare them, concretely.

At first sight they look related, they seem to have the same fundamental genes, say like an elephant (NTC) has almost all genes in common with a mouse (TC). They are both graph rewrites systems, they both use almost the same family of graphs (details later), they both speak about computation:

- in the NTC article case it is about quantum computing, there is also a practical computing arm, the Quantomatic project
- in the TC article case is about distributed, decentralized computing, and there is the distributed GLC project.

The goals are different, the means are different, the NTC camp is much more developed than the TC camp, the question is:

Is there anything fundamentally different in the TC camp?

The answer is YES. There are several fundamentally different things in the TC camp, maybe the biggest among them being the different role played by graph rewrites, summarized as NTC vs TC.

Let’s see in more detail, by comparing ZX with chemlambda.

In order to see what is really different, it is useful to make the two formalisms as alike as possible. I shall start by discussing if there is any difference between the graphs which appear in ZX from the ones which appear in chemlambda.

The graphs from ZX don’t have oriented arrows, but instead there is a global orientation convention, say from up to down when represented on page.

In ZX here is also a global horizontal “simultaneity” of graphical elements, which is part of the recipe of associating to a ZX graph an object related to a Hilbert space.

In chemlambda the graphs have oriented arrows. There is no global arrow orientation, nor any horizontal simultaneity.

Otherwise, both in ZX and chemlambda are used loops, free arrows and “half-arrows”.

So, there is an obvious procedure to associate to a graph in chemlambda a graph from ZX, by adding to the graph in chemlambda a global arrow orientation and a horizontal simultaneity.

This means, for example that the graph of the K combinator from chemlambda is represented in ZX like this:

The price is that in ZX there are several new graphical elements which need to be introduced, like the CAP, the CUP and the CROSS. Here is the list of all graphical elements needed to represent chemlambda graphs in ZX.

What about the graph rewrites? Is not clear to me if the chemlambda graph rewrites can be done as finite sequences of ZX graph rewrites, but this is not very important for this discussion. There seems to be anyways a kind of a fundamental alphabet of graph rewrites which keeps appearing everywhere. I shall not be worried about the detailed graph rewrites, but however here is how the FAN-IN and the beta moves from chemlambda appear in ZX translation.

It is worthy to mention that the global arrow orientation and the horizontal simultaneity used in ZX introduces new moves to (the translation of) chemlambda graphs which are related to these constraints, and which are not needed in chemlambda.

Now we are close to see the differences.

There is a recipe for associating to each graph from ZX an object on a Hilbert space. This is done by using the global arrow orientation convention and the horizontal simultaneity, along with a dictionary which associates to any graphical element from ZX something from a Hilbert space.

Here is the important thing about the NTC ideology: if two graphs and have the property that we can go from to by a finite sequence of ZX graph rewrites, then .

Each graph from ZX represents a computation. The graph rewrites from ZX are used to prove that TWO computations are equivalent.

More than this: a graph from ZX represents a computation in the sense that the global arrow orientation is a global time orientation, the horizontal simultaneity express space simultaneity, the CAP is a preparation, the CUP is a measurement. The nodes of the graph are GATES and the arrows of the graph are WIRES which transmit some signals.

That is why, in the NTC camp the graph rewrites DO NOT COMPUTE. The graph rewrites are used to prove an equivalence of two computations, like for example in the case of graphs which represent quantum teleportation protocol.

Now, in chemlambda, a graph is NOT a computation. Each graph is like a chemical molecule, with nodes as atoms and arrows as bonds. There is only one computation in chemlambda, which is done by graph rewrites.

So, even if we can translate chemlambda graphs into ZX graphs, there is this difference.

Suppose is a ZX graph which is obtained by translating a chemlambda graph, as previously explained. Let be another such graph. Suppose that we can arrive from to by a sequence of translations of chemlambda moves (graph rewrites), maybe also by using some of the supplementary “topological” moves which we need in ZX because of the global orientation and simultaneity constraints.

What do we have in ZX?

The graphs and represent two computation which are equivalent.

What do we have in chemlambda?

The graphs and represent the beginning and end of a computation done by the graph rewrites which in ZX serve to prove equivalence of computations.

This very big difference between NTC and TC has a big effect in all the rest of the formalisms.

______________________________________________

The key is this statement: “The graphs G and G’ represent the beginning and end of a computation done by the graph rewrites which in ZX serve to prove equivalence of computations.”

This looks like a theorem relating local computations to spatio-temporal relations!

You can certainly translate from TC to NTC, by adding the supplementary global constraints and moves, and you may get interesting mathematical results. Is the translation meaningful? I don’t know, but it is worthy to explore.

It might be possible to explore Curry-Howard Correspondence implications using the TC -> NTC translation, i.e. theorem proving.