I-don’t-always advantage of the chemical concrete machine

… over other computing formalisms, is contained in the following wise words:

Indeed, usually a FAN-OUT gate is something which has a variable as an input and two copies of it as an output. That is why FAN-OUT gates are not available in any model of computation, like for example in quantum computing.

But if you don’t use variable (names) and there’s nothing circulating through the wires of your computer model, then you can use the FAN-OUT gate, without  impunity, with the condition to have something which replaces the FAN-OUT behaviour, without it’s bad sides.  Consider graph rewriting systems for your new computer.

This is done in the chemical concrete machine, with the help of DIST enzymes and associated moves (chemical reactions). (“DIST” comes from distributivity.)

In graphic lambda calculus, the parent of the chemical concrete machine, I proved that combinatory logic can be done by using local moves available and one global move, called GLOBAL FAN-OUT.  This global move is what is resembling the most with the behaviour of a usual FAN-OUT gate:  A graph $A$ connected to the input of a FAN-OUT gate is replaced by two copies of the graph.

That’s bad, I think, so in the chemical concrete machine I arrived to prove that GLOBAL FAN-OUT can be replaced, as concerns graphs (or molecules, in the chemical concrete machine formalism) which represent combinators, with successions of local DIST moves (and some other local moves) .

It is possible exactly because there are no variable names. Moreover, there’s something almost biological in the succession of moves: we see how combinators reproduce.

As an illustration, the following is taken from the post  Chemical concrete machine, detailed (V) :

Here are the four “molecules” which represent the combinators B, C, K, W.  (Via the red-green vs black-white change of notation, they can be deduced from their expressions in lambda calculus by the algorithm described here . )

Let’s see how the “molecule” K behaves, when connected to a FAN-OUT gate (green node with one input and two outputs):

The “reproduction” of the molecule B is more impressive:

In the formalism of the chemical concrete machine, $\delta^{+}$ is a distributivity move (or “enzyme” which facilitates the move in one direction, preferentially), and $\phi^{+}$ is a FAN-IN move (facilitated in one direction).

___________________________

___________________________

This makes me believe that, as long as we don’t reason in terms of states (or any other variables), it is possible to have FAN-OUT gates in quantum computation.

Towards qubits: graphic lambda calculus over conical groups and the barycentric move

In this post I want to pave the way to the application of graphic lambda calculus to the realm of quantum computation. It is not a short, nor too lengthy way, which will be explained in several posts. Also, some experimentation is to be expected.

Disclaimer: For the moment it is not very clear to me which are the exact relations between the approach I am going to explain and linear lambda calculus or the  lambda calculus for quantum computation.  I expect a certain overlapping, but maybe not as much as expected (by the specialist in the field). The reason is that the instruments and goals which I have come from fields apparently far away from quantum computation, as for example sub-riemannian geometry, which is my main field of interest (however, for an interaction between sub-riemannian geometry and computation  see  L_p metrics on the Heisenberg group and the Goemans-Linial conjecture, by James R. Lee and Asaf Naor). Therefore, I feel the need to issue such a disclaimer for the narrow specialist.

Background for his post:

• The page Graphic lambda calculus
•  [1] Infinitesimal affine geometry of metric spaces endowed with a dilatation structure, Houston J.  Math., 36, 1 (2010), 91-136, arXiv:0804.0135.
• [2]  On graphic lambda calculus and the dual of the graphic beta move, arXiv:1302.0778.

Affine conical spaces. In the article [1] they appear under the name “normed affine group spaces”, definition 3. We may use the same type of arguments as the ones from emergent algebras   in order to get rid of the need to have a norm on such spaces.  Instead of anorm we shall put an uniformity on such a space, such that the topology associated to the uniformity makes the space to be locally compact.

Theorem 2.2 [1] characterizes affine conical spaces as self-distributive emergent algebras. The relations satisfied by self-distributive emergent algebras, if graphically represented by gates in graphic lambda calculus, are the following:

Notice that I don’t want to use the dual of the graphic beta move ([2], section 8), which is simply too powerful in this context (see [2] section 10). That is why I use instead the move R3a (which is a composite of dual beta moves). Another instance of this choice will be explained in a future post, having to do with the distributivity of the emergent algebra operations with respect to the application and lambda gates.

The barycentric move.   In order to obtain usual affine spaces instead of their more general,  noncommutative versions (i.e. affine conical spaces), we have to add the barycentric condition. This condition appears as (Af3) in Theorem 2.2 [1].  I shall transform this condition into a move in graphic lambda calculus.

The barycentric move BAR is described by the following figure and explanation. We take the commutative group $\Gamma$, which is used to label the emergent algebra gates, as $\Gamma = K^{*}$, where $K$ is a field. (Therefore $K = \Gamma \cup \left\{ 0 \right\}$.) We have then two operations on the field $K$: multiplication $\varepsilon, \mu) \mapsto \varepsilon \mu$ and addition $(\varepsilon, \mu) \mapsto \varepsilon + \mu$. Because $K$ contains also the element $0$, the neutral element for addition, we add a new gate $\bar{0}$.  With these preparations, the BAR move is the following:

Notice that when $\varepsilon = 1$ at the left hand side of the figure appears the gate $\bar{0}$. This gate corresponds, in the particular case of a vector space, to the usual dilation of coefficient $0$. We don’t need to put this as a sort of an axiom, because we can obtain it as a combination of the BAR move and ext2 moves. Indeed:

Knowing this, we can extend the emergent algebra moves R1a, R1b and R2 to the case $\varepsilon = 0$. Here is the proof. For R1a we do this:

The move R1b, for the degenerate case $\varepsilon = 0$, is this:

Finally, for the move R2 we have two cases, corresponding to $0 \, \varepsilon = 0$ and $\varepsilon \, 0 = 0$. The first case is this:

The second case is this:

Final remark: The move BAR can be seen as analogous of an infinite sequence of moves R3 (but there is no rigorous sense for this in graphic lambda calculus). Indeed, this is related to the fact that $\frac{1}{1-\varepsilon} = \sum^{\infty}_{0} \varepsilon^{k}$.  See [1] section 8 “Noncommutative affine geometry” for the dilation structures correspondent of this equality and also see the post Menelaus theorem by way of Reidemeister move 3.