# Tales told by coloured tangles

Daniel Moskovich and Avishy Y. Carmi  Faculty of Engineering Sciences & Center
for Quantum Information and Technology
Ben-Gurion University of the Negev, Beer-Sheva 8410501, Israel

###### Abstract.

Tangle machines are a topologically inspired diagrammatic formalism to
describe information flow in networks. This paper begins with an expository
account of tangle machines motivated by the problem of describing ‘covariance
intersection’ fusion of Gaussian estimators in networks. It then gives two
examples in which tangle machines tell stories of adiabatic quantum
computations, and discusses learning tangle machines from data.

##  1\. Introduction

The Kantian explanation for ‘the unreasonable effectiveness of mathematics in
the natural sciences” is that the patterns which we seek out in nature are
those patterns with which we are already familiar as innate categories of
perception [33]. When we encounter a new phenomenon, perhaps we first seek to
describe this phenomenon in the category of perception most familiar to us.
Taken one step further, perhaps human choice of research topics is itself
influenced by the scientific language of the day.

The conventional graphical language in computer science is the language of
flowcharts (e.g. [5]). A flowchart is a labeled directed graph in which edges
represent transitions that can be concatenated. Thus, an ordered sequence of
edges $(e_{1},e_{2},\ldots,e_{k})$ in which the head of $e_{i}$ is the tail of
$e_{i+1}$ for all $i=1,2,\ldots,k-1$ represents a transition from the tail of
$e_{1}$ to the head of $e_{k}$. Edges can be prepended or appended to such
sequences, and the transition represented by prepending $e_{1}$ to
$(e_{2},e_{3},\ldots,e_{k})$ is guaranteed to coincide with the transition
represented by appending $e_{k}$ to $(e_{1},e_{2},\ldots,e_{k-1})$. This
property is called _associativity_. Thus, the language of flowcharts natively
describes _sequential_ processes, although this paradigm may be expanded via a
_concurrency symbol_.

In previous work we proposed a different diagrammatic formalism called _tangle
machines_. A tangle machine looks visually similar to a coloured tangle
diagram in low dimensional topology [10, 11, 12, 13, 14]. It consists of arcs
which we think of as analogous to computer registers and of crossings that we
call _interactions_ which we think of as analogous to logic gates. The
interaction below involves three arcs called an _agent_ , an _input patient_ ,
and an _output patient_. The interaction is labeled by a binary operation
$\triangleright$, and for labels $x$ for the input patient and $y$ for the
agent, the label of the output patient is $x\triangleright y$.

(1.1)

We call operation $\triangleright$ a _fusion_ if it satisfies three
properties:

  1. (1)

$x\triangleright x=x$ for all $x$. Thus, fusing information with itself should
be the identity operation.

  2. (2)

An input label can uniquely be recovered from its corresponding output label
together with the agent label. Thus, fusion should ‘not forget’.

  3. (3)

Fusing $x\triangleright z$ with $y\triangleright z$ should equal
$(x\triangleright y)\triangleright z$. Thus, fusion should count the redundant
appearance of $z$ only once towards the final result.

The language of tangle machines natively describes networks of fusions
(strengthening the requirement that the fusion ‘not forget’ strengthened to
$\bullet\triangleright y$ being a bijection). There is nothing inherently
sequential about fusions, so tangle machines and flowcharts are quite
different. What is the expressive power of tangle machines? More prosaically,
what tales can a tangle machine tell?

Let us adopt an abstract view of a computation as a scheme to apply the
information content of a computer program to the information content of input
data in order to generate output data. Some computations (in this generalized
sense) are fusions. It turns out that we can describe any Turing machine by a
tangle machine under this paradigm. If we limit the number of interactions
then we can describe any computation in the complexity class $\mathrm{IP}$
[12]. Parenthetically, we don’t know how much more we can describe by tangle
machines— for example, can tangle machines with bounded interactions describe
any computation in complexity class $\mathrm{MIP}$?

What more can be described by tangle machines? Archetypal mathematical
examples of fusions are convex combinations and group conjugations, but we
suggest that an archetypal real-world example of a fusion operation is fusion
of estimates of a random variable. If the random variable follows a Bernoulli
distribution then estimator fusion and convex combination essentially coincide
(an example of this is in [12]). We consider fusion of normally distributed
estimates. The Kalman filter is a linear optimal measure to fuse Gaussian
estimates, but it requires knowledge of how the estimate errors depend on one
another. This information is not contained in the estimates themselves and may
sometimes be entirely unknown. _Covariance intersection_ is a method to fuse
Gaussian estimates whose error cross-correlations are unknown. Section 2
introduces tangle machines as a diagrammatic language for information flow in
networks in which information is fused by covariance intersection. It contains
a geometric interpretation of covariance intersection as a choice of a point
on a geodesic on a _statistical manifold_ whose points parameterize normal
distributions.

Section 3 explains the connection of tangle machines to low dimensional
topology. Section 3.1 recalls a diagrammatic algebra from low dimensional
topology. Section 3.2 generalizes and discusses quandles, after which Section
3.3 defined tangle machines and shows how they may describe information fusion
networks. The above sections represent an expository account of previous
published work of the authors. As discussed in [14], tangle machines (with
colours suppressed) topologically arise as diagrams of embedded networks of
intervals and spheres in standard Euclidean $4$–space.

Section 4 takes tangle machines into the realm of quantum information,
presenting several adiabatic quantum computations (AQC’s) with different
performance features. Section 4.2 presents a computation in which a product
state evolves into an entangles state, and Section 4.3 presents a Boolean
$2$–SAT problem over four qubits. A further example may be found in [13,
Section 5].

Section 5 discusses potential utility of the tangle machine description.
Inherited from low dimensional topology, tangle machines have topological
invariants that are characteristic quantities giving high-level information
about what is happening in the machine [11, 14]. In particular, there are
meaningful notions of _capacity_ and of _complexity_ for tangle machines. In
addition, tangle machines provide a flexible description, and this flexibility
may perhaps be useful for fault tolerance [10].

Section 6 concludes by discussing the problem of adapting existing causality-
detection algorithms to detect tangle machines. We illustrate with an example
in which we detect a single crossing in real-world Google search data.

Figure 1.  A coloured tangle representing this paper. At each crossing, the
output topic is an application of the input topic to the agent (overcrossing)
topic, perhaps in a different sense for each crossing. This figure suggests
how a coloured tangle can tell a tale and has no rigourous mathematical
meaning.

The father of the use of tangle diagrams as a diagrammatic language for
computation is Louis Kauffman, who represented automata, nonstandard set
theory, and lambda calculus with tangle diagrams [29, 30, 8]. Buliga has
suggested to represent computations using a different calculus of coloured
tangles [7]. In another direction, a different diagrammatic calculus,
originating in higher category theory, has been used in the theory of quantum
information— see e.g. [1, 4, 39]. In all of these approaches an element in a
topologically inspired diagrammatic algebra represents a computation and
equivalent diagrams represent bisimilar computations. Tangle machines are
distinguished by the role of colours, by locality of orientations, and by
binding together of operations in ‘interactions’, as discussed in [13].

#### Acknowledgement

D.M. was partially supported by the Helmsley Charitable Trust through the
Agricultural, Biological and Cognitive Robotics Initiative of Ben-Gurion
University of the Negev.

##  2\. An information geometric view of covariance intersection

###  2.1. Information geometry

Information geometry applies the methods of differential geometry to
probability theory [3]. Its main role so far has been to provide geometric
coordinate-free elucidation to known facts. For example, the Cramér–Rao
inequality over $\mathds{R}$ which bounds variance from below by the
reciprocal of Fisher information becomes a statement about the statistical
manifold changing more in the vicinity of points of high curvature than in the
vicinity of points of low curvature.

A _statistical manifold_ corresponding to an $n$–parameter family of
distributions has a point for each possible value of the parameters. In
particular, the statistical manifold for all normal distributions over
$\mathds{R}$ is a surface whose coordinates are $(\mu,\sigma^{2})$, the order
and the variance of the distribution. A statistical manifold has a Riemannian
metric called the _Fisher information metric_. In the case of Gaussian random
variables the metric is given by the inverse of the covariance matrix (over
$\mathds{R}$ by the reciprocal of the variance as in the Cramér–Rao bound).

We will be considering the problem of estimate fusion in an information
geometric setting. The estimates will be points on the statistical manifold.
Our main observation will be that that a fusion corresponds to a choice of a
point on a geodesic.

###  2.2. Estimator fusion

In this section we ask the question: How can we fuse estimates of an unknown
quantity whose interdependence is unknown?

Consider a pair of sensors which provide noisy observations about an unknown
state vector $X$. Each sensor runs its own filtering algorithm to yield an
estimate $X_{1,2}$ of $X$ and an estimate $C_{1,2}$ of the error covariance
matrix of $X$.

(2.1)
$\mathrm{cov}\left[X-\hat{X}_{i}\right]\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}E\left[(X-\hat{X}_{i})(X-\hat{X}_{i})^{T}\right]\\\
-E\left[X-\hat{X}_{i}\right]E\left[X-\hat{X}_{i}\right]^{T}\quad\text{$i=0,1,2$}\enspace.$

We wish to optimally integrate these estimates
$\left(\hat{X}_{1},C_{1}\right)$ and $\left(\hat{X}_{2},C_{2}\right)$. It is
important that the fused estimate be _consistent_ (or _conservative_), meaning
that:

(2.2) $C_{i}\geq\mathrm{cov}\left[X-\hat{X}_{i}\right]\enspace,$

i.e. that the matrix difference $C_{i}-\mathrm{cov}\left[X-\hat{X}_{i}\right]$
is positive semi-definite. We would like all estimators to be consistent
because inconsistent estimators may diverge and cause errors.

If the correlations between the estimate errors are known, a linear optimal
fusion in the sense of minimum mean estimation error (MMSE) is given by the
_Kalman filter_. But such error cross-correlations are typically unknown and
may be unmeasurable in real-world settings. Ignoring error cross-correlations
can cause the Kalman filter estimates to be non-conservative and perhaps to
diverge [15]. The standard approach in applications is to increase the system
noise artificially. But proper use of this heuristic requires substantial
empirical analysis and compromises the integrity of the Kalman filter
framework [35].

_Covariance intersection_ provides a method to fuse estimates whose error
cross-correlations are unknown in a way that guarantees that the resulting
estimate is consistent [28]. The covariance intersection method to fuse
estimators $\left(\hat{X}_{1},C_{1}\right)$ with
$\left(\hat{X}_{2},C_{2}\right)$ requires a choice of _weight_
$\omega\in(0,1)$. The bottleneck for practical covariance intersection is the
computation of the optimal value for the weight $\omega$ with respect to some
(typically nonlinear) cost function such as logdet or trace [16, 24]. In the
present paper we treat $\omega$ as a formal parameter or as an unknown
constant for each pair of estimates to be fused.

We denote the covariance intersection of $\left(\hat{X}_{1},C_{1}\right)$ with
$\left(\hat{X}_{2},C_{2}\right)$ with respect to $\omega\in(0,1)$ as follows:

(2.3)
$\left(\hat{X}_{a},C_{a}\right)_{\omega}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\left(\hat{X}_{1},C_{1}\right)\triangleright_{\omega}\left(\hat{X}_{2},C_{2}\right)\enspace.$

We construct $\left(\hat{X}_{a},C_{a}\right)_{\omega}$ as follows:

(2.4a) $\hat{X}_{a}=(1-\omega)C_{a}C_{1}^{-1}\hat{X}_{0}+\omega
C_{a}C_{2}^{-1}\hat{X}_{1}\enspace,$ (2.4b)
$C_{a}^{-1}=(1-\omega)C_{1}^{-1}+\omega C_{2}^{-1}\enspace.$

The working principle of covariance intersection is that it fuses two
conservative estimates into a third conservative estimate. The reason, for
Gaussian estimators, is that the _covariance ellipse_ of the fused estimator
includes the intersection of the covariance ellipse of the estimators being
fused (Figure 2). A _covariance ellipse_ of a covariance matrix $C$ is the
locus of vectors $v$ such that $v^{\,T}C^{-1}v\leq a$ where $a$ is some
arbitrary (but fixed) constant. For Gaussian estimators, $C^{-1}$ represents
the Fisher information. For details see [28].

Figure 2.  The covariance ellipse of the fused estimator is a minimal ellipse
that includes within it the intersection of the covariance ellipses of the
estimates being fused.

We prove the following proposition in the appendix.

######  Proposition 2.1.

The $1$–parameter family of Gaussian covariance intersections
$\left(\hat{X}_{a},C_{a}\right)_{\omega\in[0,1]}$ parameterizes the geodesic
from $\left(\hat{X}_{1},C_{1}\right)$ to $\left(\hat{X}_{2},C_{2}\right)$.

Figure 3.  A basic information fusion operation (left) and its geometric
representation (right). Here $p(x)$ denotes a Gaussian distribution with mean
$\hat{X}$ and covariance matrix $C$, which represents a point in the manifold.

###  2.3. Properties of covariance intersection

Covariance intersection has the following properties, which are evident from
the geometric interpretation and can also be derived directly from (2.4):

Idempotence:

$a\triangleright_{\omega}a=a\qquad\text{for any estimator $a$ and for any
$\omega\in(0,1)$.}$

Reversibility:

The function $\bullet\triangleright_{\omega}b$ from the statistical manifold
to itself is a bijection. Thus, an estimate $a$ can uniquely be recovered from
$b$, $a\triangleright_{\omega}b$, and $\omega$.

No double counting:

For any estimators $a$, $b$, and $c$ and for any weights
$\omega,\omega^{\prime}\in(0,1)$, we have:

(2.5)
$(a\triangleright_{\omega^{\prime}}b)\triangleright_{\omega}c=(a\triangleright_{\omega}c)\triangleright_{\omega^{\prime}}(b\triangleright_{\omega}c)\enspace.$

Thus, the redundant appearance of $c$ in $a\triangleright_{\omega}c$ and in
$b\triangleright_{\omega}c$ counts only once towards the final result. This is
the key property of covariance intersection that makes it insensitive to the
dependence of different estimators.

##  3\. Coloured tangle diagrams in low dimensional topology

This section provides a new strand in our tale. Thus, we shall put aside all
that came before, and we shall begin afresh.

###  3.1. Colouring knots and tangles

The fundamental problem in knot theory is to distinguish knots, which are
smooth embeddings $K\colon\,S^{1}\rightarrow S^{3}$ of a directed circle into
the $3$–sphere, considered up to an equivalence relation called _ambient
isotopy_. Identifying $S^{3}\simeq\mathds{R}^{3}\cup\\{\infty\\}$ and choosing
a projection of the knot onto a generic plane in $\mathds{R}^{3}$ disjoint
from the knot, we may represent $K$ as a _knot diagram_ such as one of those
drawn in Figure 4. _Reidemeister’s Theorem_ tells us that two knot diagrams
represent ambient isotopic knots if and only if they are related by a finite
sequence of the three _Reidemeister Moves_ of Figure 5.

A

B

C

Figure 4.  The unknot, the trefoil, and the figure-eight knot. Figure 5. The
Reidemeister moves. Orientations are arbitrary. To execute a Reidemeister
move, cut out a disc inside a tangle diagram containing one of the patterns
above, and replace it with another disc containing the pattern on the other
side of the Reidemeister move.

How are we to distinguish two non-ambient-isotopic knots? For example, how are
we to distinguish the _trefoil knot_ from the _unknot_ in Figure 4? The
original idea of Tietze [38], as explained later by Fox [23], is to colour
each arc in the knot diagram in one of three colours $\\{\text{red, blue,
green}\\}$, represented numerically as $0$, $1$, and $2$, subject to the
constraints that at least two different colours are used, and if two adjacent
colours to a crossing are $i$ and $j$ then the third adjacent colour is
$i\triangleright j\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}2i-j\bmod
3$.

(3.1)

The trefoil can be coloured according to these rules (Figure 6), but the
unknot and the figure-eight knot cannot. This property of being _$3$
–colourable_ is preserved under Reidemeister moves (Figure 12 will later show
a more general statement), and thus we have shown that the trefoil is knotted
and is not ambient isotopic to the figure-eight knot. But how to show that the
figure-eight knot is knotted? Simple. Take five colours $0$, $1$, $2$, $3$,
and $4$, and colour according to the same procedure. The figure-eight knot is
$5$–colourable, but the trefoil and the unknot are not.

Generalizing, we arrive at the idea of defining an algebraic structure by
which a knot can be coloured. Its elements are a set $Q$ and it comes equipped
with an operation $\triangleright$ satisfying the following axioms:

Idempotence:

$x\triangleright x=x\qquad\forall\ x\in Q\enspace.$

Automorphism:

The function:

$\displaystyle\triangleright\,z\colon\ Q\ $ $\displaystyle\to\ Q$
$\displaystyle x\ $ $\displaystyle\mapsto\ x\triangleright z\enspace,$

is an automorphism of $(Q,\triangleright)$ for all $z\in Q$. In particular it
is a bijection of sets and:

(3.2) $(x\triangleright y)\triangleright z=(x\triangleright
z)\triangleright(y\triangleright z)\qquad\forall x,y,z\in Q\enspace.$

A structure $(Q,\triangleright)$ is called a _quandle_ (e.g. [27]). Several
examples will be given in Section 3.3.

A

B

C

Figure 6.  A trivial colouring of the unknot, a $3$–colouring of the trefoil,
and a $5$–colouring of the figure-eight knot. The quandle operation is
$i\triangleright j=2j-i\bmod p$.

###  3.2. Generalizing coloured knots

We did not use all of the properties of a knot when defining a quandle
colouring. As far as colourings are concerned, several properties of a knot
were irrelevant. Let us relax these, with a view to motivating tangle machines
in Section 3.3.

  * •

We did not care about the number of connected components or whether they were
closed. Quandle colourings are defined for _tangles_ , that are
_concatenations_ of crossings, i.e. shapes composed by scattering crossings in
the plane and connecting up endpoints via disjoint line segments (Figure 7
shows how a knot diagram can be constructed this way).Two tangles are
equivalent if they are related by Reidemeister moves. See Figure 8.

  * •

We did not care about planarity. In terms of colourings, nothing is lost by
allowing the connecting segments to intersect transversely. Relaxing the
planarity requirement gives rise to _virtual tangles_.

  * •

The orientations of the arcs were only important to give directionality to the
quandle operation— to specify which the ‘input underarc’ is, versus the
‘output underarc’. There is no reason for directions of overcrossing arcs to
match up; a global direction on an arc plays no role. Restricting orientations
to overcrossing arcs and making them local introduces ‘disorientations’ into
our virtual tangles (e.g. [17])

Figure 7.  A knot formed by concatenating crossings. Orientations ignored.

A

B

Figure 8.  Two equivalent tangles.

We will also want to consider quandles in a more general sense, in which $Q$
comes equipped with not one, but an entire family $B$ of binary operations,
subject to the following axioms:

Idempotence:

$x\triangleright x=x\qquad\forall\ x\in Q\quad\forall\ \triangleright\in
B\enspace.$

Automorphism:

The function:

$\displaystyle\triangleright\,z\colon\ Q\ $ $\displaystyle\to\ Q$
$\displaystyle x\ $ $\displaystyle\mapsto\ x\triangleright z\enspace,$

is an automorphism of $(Q,B)$ for all $z\in Q$ and for all $\triangleright\in
B$. In particular each such function is a bijection of sets, and:

(3.3) $(x\blacktriangleright y)\triangleright z=(x\triangleright
z)\blacktriangleright(y\triangleright z)\qquad\forall\ x,y,z\in
Q\quad\forall\triangleright,\blacktriangleright\in B\enspace.$

Such structures, perhaps subject to extra axioms which hold in our cases of
interest, are variously called _distributive $\Gamma$–idempotent right
quasigroups_ [6], _$G$ –family of quandles_ [25], and _multiquandles_ [37]. We
continue to call them quandles.

We list some examples of quandles:

######  Example 3.1 (Conjugation quandle).

Colours might be elements of a group $\Gamma$, and the operation might be
conjugation:

(3.4) $x\blacktriangleright y\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}y^{-1}xy\enspace.$

The pair $(\Gamma,\left\\{\blacktriangleright\right\\})$ is called a
_conjugation quandle_. If the group $\Gamma$ is a dihedral group and we colour
by reflections, we recover the notion of an $n$–colouring of a knot. e.g.
[23].

######  Example 3.2 (Linear quandle).

Colours might be elements of a real vector space $Q$ and the operations might
be convex combinations:

(3.5) $x\triangleright_{\omega}y\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}(1-\omega)x+\omega y\qquad\omega\in
D\subseteq\mathds{R}\setminus\left\\{1\right\\}\enspace.$

The pair $\left(Q,\left\\{\triangleright_{\omega}\right\\}_{\omega\in
D}\right)$ is called a _linear quandle_.

######  Example 3.3 (Loglinear quandle).

In the same setting as Example 3.2, consider the operations:

(3.6) $x\,\bar{\triangleright}_{\omega}\,y\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}x^{1-\omega}y^{\omega}\qquad\omega\in
D\subseteq\mathds{R}\setminus\left\\{1\right\\}\enspace.$

The pair $\left(Q,\left\\{\bar{\triangleright}_{\omega}\right\\}_{\omega\in
D}\right)$ is called a _loglinear quandle_.

###  3.3. Tangle machine definition

The attentive reader will have noticed that the properties of covariance
intersection are similar to the quandle axioms. As we have seen, the set of
points of a statistical manifold of Gaussian distributions satisfies the
quandle axioms with respect to covariance intersection ‘choose a point on a
geodesic’ operations. In this section, we define tangle machines and colour
them by estimators. Quandle operations will be covariance intersections.

The basic building block of tangle machine is called an _interaction_ (Figure
9). It involves one strand coloured $y$ which we call a _agent_ and strands
coloured $x_{1},x_{2},\ldots,x_{k}$ which we call _patients_. We draw $y$ as a
thick horizontal line, and we label line segments above $y$ by
$x_{1},x_{2},\ldots,x_{k}$ correspondingly. An interaction has a weight $s$
associated to it, and the strands below $y$ are labeled by
$x_{1}\triangleright_{s}y,x_{2}\triangleright_{s}y,\ldots
x_{k}\triangleright_{s}y$ correspondingly. We may orient the strand labeled
$y$ or all strands labeled $x$ (these two conventions are interchangeable).
Sometimes we may be sloppy and orient both, in which case the orientations of
the patients should be ignored.

Figure 9.  An interaction. We usually draw agents as thick lines.

Interactions may be concatenated as shown in Figure 10. When labels are
estimators, the concatenation of interactions represents a pair of related
choices of points on geodesics, as shown in Figure 11.

One reason that we allow multiple input patients for interactions is that the
covariance intersection parameter $\omega$ is an estimated quantity. In
general it will be different for different estimator fusions. When we know
that it is the same, this information is important for us and we would like to
record it. We typically represent agents with multiple agents by thickening
the overarc.

Figure 10.  Concatenation. Endpoints can be concatenated if they share the
same colours (colours are suppressed in the above figure). At the third stage,
note that in our formalism, only agents are oriented, and no compatibility
requirement is imposed. The concatenation line chosen is arbitrary, and in
particular it may intersect other concatenation lines.  Figure 11.  An
information fusion network – a tangle machine (left) and its geometric
representation on a statistical manifold (right).

The lines used for concatenation do not matter, and the equivalence relation
on diagrams generated by different choices of concatenating lines, and changes
of local orientation, and adding or removing agents where ‘nothing happens’,
is illustrated in Figure 14. The first two moves allow us to ignore
orientations of agents when they don’t matter.

Reidemeister moves for machines are illustrated in Figure 12, where the
general form of R3 is obtained in Figure 13 where we first replace a box by a
thickened line for convenience. We follow this convention for the remainder of
the paper.

R1

R2

R3

Figure 12.  The Reidemeister Moves, which are local modifications of
information fusion networks. The moves are considered for all orientations on
all edges. The properties of information fusion guarantees that the underlined
colours on the LHS and on the RHS are equal and thus that these local moves
are well-defined. In the R2 move, $\triangleleft$ represents the implicitly
defined inverse operation to $\triangleright$. Only a special case of R3 is
illustrated above— the general case is given by Figure 13.

Figure 13.  The general R3 move. Figure 14.  Cosmetic moves for machines.
Where directions are not indicated, the meaning is that the move is valid for
any directions, and the same for colourings. Here, $\triangleleft$ denotes the
(implicitly defined) inverse operation to $\triangleright$.

One notion of tangle machine computation is that it is a choice of arcs as
_input registers_ and another choice of arcs as _output registers_. Local
moves may not involve these registers. If the colours of the input registers
uniquely determine the colours of the output registers, then we consider this
determination as a computation. We may think of interactions as being
analogues to that of logic gates. But because interaction concatenation is
non-sequential (an interaction may even be concatenated to itself), this
notion of computation is also non-sequential, and a tangle machine computation
may be thought of as taking place ‘all at once’ via an oracle.

When interactions represent choice of point on a geodesic between the input
patient and the agent on a statistical manifold, machines represent a network
of these.

##  4\. Tangle machines coloured by Hamiltonians

###  4.1. Tangle machines representing piecewise adiabatic quantum
computations

Quantum information is based on quantum probability theory, in which _density
matrices_ take the place of classical probability distributions. A set of
density matrices may be given the structure of a statistical manifold. A
tangent vector to this manifold is a _Hamiltonian matrix_ , which physically
describes the dynamics of a quantum system.

One research direction would be to colour tangle machines by density matrices
and to fuse them using points on the geodesic between them on the statistical
manifold. Instead, we colour our machines by Hamiltonians and we consider the
linear quandle with operations indexed by a time parameter $s\in(0,1)$ [13].

Adiabatic quantum computation (AQC) considers evolving Hamiltonians of the
form $(1-s)H_{0}+sH_{1}$ to perform quantum computation [20]. Analogously to
(2.4) in which the statistical moments of two estimators are fused, the
interaction with output:

(4.1) $H_{s}=H_{0}\triangleright_{s}H_{1}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}(1-s)H_{0}+sH_{1}\enspace,$

may be viewed as a fusion of two statistical ensembles underlying two quantum
systems. As before the parameter $s\in(0,1)$ determines the contribution of
each component to the new ensemble, $H_{s}$.

The quantum mechanical counterpart of independence of estimators is that the
Hamiltonians commute, $[H_{0},H_{1}]=0$, in which case the underlying density
matrices satisfy:

(4.2) $\rho_{s}\propto\exp\left(-\beta H_{s}\right)=\exp\left(-\beta
H_{0}\right)^{1-s}\exp\left(-\beta
H_{1}\right)^{s}\propto\rho_{0}^{1-s}\rho_{1}^{s}\enspace.$

This is analogous to the formula for a geodesic on a statistical manifold in
Section 2.

The idea of AQC is to evolve a Hamiltonian $H_{0}$ representing a problem
whose solution (the ground state) is easy, into a different and perhaps more
complicated Hamiltonian $H_{1}$ whose ground state is the solution to the
computational task of interest. The computation initializes the system in its
ground state, the ground state of $H_{0}$, and then slowly evolves its
Hamiltonian to $H_{1}$. This process is called _quantum annealing_. By the
Adiabatic Theorem, the system remains in its ground state throughout the
evolution process, and the computation concludes at the ground state of
$H_{1}$, that is the sought-after solution. The _computing time_ of an AQC is
inversely proportional to the square of the minimal energy gap between the
ground state and the rest of the spectrum, namely to the square of
$g\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\lambda_{1}-\lambda_{0}$,
where $\lambda_{i+1}\geq\lambda_{i}$ are the underlying energy eigenvalues of
the Hamiltonian. Our objective is thus to maximize the minimal $g$ along the
evolution path or to minimize the computation time.

As shown in a previous paper [13] and as we will again illustrate below, a
tangle machine may be used to represent a piecewise-defined evolution path of
a Hamiltonian. It is well-known that nonlinear evolution paths speed up
quantum computation [21, 22]. The topology of the machine itself is only of
interest if we can measure its colours at intermediate times and at
intermediate arcs. The technological barrier to implementation is the _no-
cloning theorem_ which tells us that we cannot copy a state, and therefore we
have lost it the moment we have measured it. From a future technological
perspective we might envision a solution in which concatenation of
interactions occurs by means of _quantum teleportation_ of an entire
Hamiltonian from one interaction to the next. In such a case the tangle
machine representation of an AQC would have all of the same features as a
tangle machine representation of a classical information fusion network.
Without such technology, the tangle machines below merely tell us a tale of
Hamiltonian evolution.

We define one additional piece of structure. Choose a _time deformation
parameter_ $\alpha\in(0,1)$ and define the normalized time variables:

(4.3) $t_{i}=\min\\{1,\alpha^{-i}t\\},\quad i=0,1,2,\ldots$

with $t\in(0,1)$. A time parameter $t_{i}$ is associated with the _$i$ -th
time-frame_, and by convention all interactions within this ‘time-frame’
(drawn as a region in the plane) are labeled $t_{i}$. For small $\alpha$, the
computations in the $k$-th time-frame nearly terminate when the computations
in the $k-1$ frame begin. In the limit $\alpha\to 0$ we recover sequential
computation.

Our diagrams are drawn along a time axis showing the time-frames. Interactions
appearing in a particular time-frame, say the $k$-th one, are understood to be
executed using the respective time parameter, i.e. $\triangleright_{t_{k}}$.
In what follows we use the shorthand $\triangleright_{k}$ for
$\triangleright_{t_{k}}$.

###  4.2. Time-Entanglement asymmetry

In this section we describe a computation involving a single pair of qubits in
which a product state evolves into an entangled state. As we shall see, the
computation time is proportional to the amount of entanglement.

We begin with a standard adiabatic computation

(4.4) $O(t)=H_{0}\triangleright_{0}H_{1}\enspace,$

where the initial and problem Hamiltonians are given by:

(4.5a)
$H_{0}=P_{x}^{0}\triangleright_{\oplus}P_{x}^{1}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}(1-a)(P_{x}^{0}\otimes 1)+a(1\otimes P_{x}^{1})\enspace;$ (4.5b)
$H_{1}=1-\left(\lambda\left|00\right\rangle+\sqrt{1-\lambda^{2}}\left|11\right\rangle\right)\left(\lambda\left|00\right\rangle+\sqrt{1-\lambda^{2}}\left|11\right\rangle\right)^{\dagger}\enspace;$

where $a,\lambda\in(0,1)$ are fixed parameters. The _projectors_ are defined
as:

(4.6) $P_{x}^{j}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\frac{1}{2}(1-(-1)^{j}X)\enspace,$

where $X$ is the Pauli X matrix. The initial ground state is the product
$\left|01\right\rangle_{x}$ whereas the final ground state is a state (written
above in the computational basis Z) whose entanglement entropy is

$S(\lambda)=-\lambda^{2}\log(\lambda^{2})-(1-\lambda^{2})\log(1-\lambda^{2})\enspace.$

A maximally entangled state is obtained for $\lambda=\frac{1}{\sqrt{2}}$.

Figure 15 graphs computation time against an increasing $\lambda$ for two
different values of $a$.

Figure 15. Computation time against $\lambda$ for two values of $a$: (Blue)
$a=0.95$, and (Red) $a=0.5$.

Let’s solve the same problem using a tangle machine and time deformation. We
choose time variables as:

(4.7) $t_{1}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}a\cdot\min\\{1,\alpha^{-1}t\\},\qquad t_{0}=t\enspace.$

Let us solve the same computational problem in two different ways, represented
by the tangle machines in Figure 16:

(4.8a) $O_{1}(t)=\left[(P_{x}^{0}\otimes 1)\triangleright_{1}(1\otimes
P_{x}^{1})\right]\triangleright_{0}H_{1}\enspace;$ (4.8b)
$O_{1}^{\prime}(t)=\left[(P_{x}^{0}\otimes
1)\triangleright_{1}H_{1}\right]\triangleright_{0}\left[(1\otimes
P_{x}^{1})\triangleright_{1}H_{1}\right]\enspace.$

The computation time is graphed with respect to $\lambda$ in Figure 17. The
performance of the standard AQC from Figure 15 is also shown for comparison.
Here $\alpha=0.5$.

Figure 16. Equivalent computations. Figure 17. Computation time against
$\lambda$ for $a=0.95$. Showing time-deformed AQC (with $\alpha=0.5$)
$O_{1}^{\prime}(t)$ (thick red), $O_{1}(t)$ (thick green), and standard AQC
$H_{0}\triangleright_{0}H_{1}$ (thin blue). The black line corresponds to no
time deformation, i.e. $\left[(P_{x}^{0}\otimes
1)\triangleright_{\star}(1\otimes P_{x}^{1})\right]\triangleright_{0}H_{1}$,
where $\triangleright_{\star}$ is executed using a time variable
$\min\\{a,t_{0}\\}$.

The difference between the two time-deformed computations, $O_{1}(t)$ and
$O_{1}^{\prime}(t)$, is evident. Figure 18 illustrates this further by showing
the gap between the computation time of either schemes with respect to
$\lambda$. We see that the discrepancy between the two computations reaches a
peak for a maximally entangled final ground state.

Figure 18. Difference in computation time between the two time-deformed
computations, $O_{1}(t)$ and $O_{1}^{\prime}(t)$. $\alpha=0.5$.

The performance of the time-deformed algorithms for $a=0.5$ and $\alpha=0.1$
are shown in Figure 19. This time the computation $O_{1}^{\prime}(t)$ has a
clear advantage over $O_{1}(t)$ and the standard AQC as the amount of
entanglement reaches its peak, around $\lambda=1/\sqrt{2}$.

Figure 19. Computation time against $\lambda$ for $a=0.5$. Showing time-
deformed AQC (with $\alpha=0.1$) $O_{1}^{\prime}(t)$ (thick red), $O_{1}(t)$
(thick green), and standard AQC (thin blue). The black line corresponds to no
time deformation, i.e. $\left[(P_{x}^{0}\otimes
1)\triangleright_{\star}(1\otimes P_{x}^{1})\right]\triangleright_{0}H_{1}$,
where $\triangleright_{\star}$ is executed using a time parameter
$\min\\{a,t_{0}\\}$.

###  4.3. 2-SAT example

In this example we consider a Boolean 2-SAT problem over four variables
(qubits). We wish to find a satisfiable assignment for the following
disjunctive normal form (DNF) expression

(4.9) $((x_{1}\wedge x_{2})\vee(\neg x_{1}\wedge\neg
x_{2}))\wedge((x_{3}\wedge x_{4})\vee(\neg x_{3}\wedge\neg x_{4}))\enspace.$

There are four such assignments, namely, $(0,0,0,0)$, $(0,0,1,1)$,
$(1,1,0,0)$, $(1,1,1,1)$. The final Hamiltonian corresponding to this problem
is composed of 2-local Hamiltonians. To see this we define the projector

(4.10) $P_{z}\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\frac{1}{2}(I-Z)\enspace,$

where $Z$ is the Pauli Z matrix. We see that:

(4.11) $P_{z}\left|x\right\rangle=x\left|x\right\rangle,\quad P_{z}\otimes
P_{z}\left|xy\right\rangle=(x\wedge y)\left|xy\right\rangle,\\\ \quad
P_{z}\oplus P_{z}\left|xy\right\rangle=(x\vee
y)\left|xy\right\rangle,\quad(1-P_{z})\left|x\right\rangle=(\neg
x)\left|x\right\rangle\enspace.$

An encoding of the above 2-SAT is then given by:

(4.12)
$H_{1}=1-\frac{1}{2}\left[P_{z}^{2}+(1-P_{z})^{2}\right]\otimes\frac{1}{2}\left[P_{z}^{2}+(1-P_{z})^{2}\right]\\\
=1-\frac{1}{4}\left[P_{z}^{4}+P_{z}^{2}(1-P_{z})^{2}+(1-P_{z})^{2}P_{z}^{2}+(1-P_{z})^{4}\right]\enspace,$

where we have used shorthands $P_{z}^{2}$ and $P_{z}(1-P_{z})$ for
$P_{z}\otimes P_{z}$ and for $P_{z}\otimes(1-P_{z})$ respectively.

The problem Hamiltonian has a degenerate ground state whose basis vectors are
satisfying assignments for our 2-SAT. Suppose there is an oracle with a
probability of $1/4$ of yielding any one of the four satisfying assignment.
This oracle is represented by a black-box Hamiltonian whose ground state is a
superposition of the four assignments. Hence,

(4.13) $H_{\clubsuit}=1-\left|v\right\rangle\left\langle
v\right|,\quad\left|v\right\rangle=\frac{1}{2}\left(\left|0000\right\rangle+\left|0011\right\rangle+\left|1100\right\rangle+\left|1111\right\rangle\right)\enspace.$

The initial Hamiltonian has a ground state $\left|0000\right\rangle_{x}$, i.e.
a superposition of $2^{4}$ possible assignments. It is given by

(4.14) $H_{0}=P_{x}^{0}\oplus P_{x}^{0}\oplus P_{x}^{0}\oplus
P_{x}^{0}\enspace.$

We describe a number of computations which solve the 2-SAT problem using the
oracle’s knowledge. These computations differ both in the way in which the
oracle’s “answers” are processed and in their evaluation of the SAT clauses.
The details are as follows. In the first round of experiments we assume that
$H_{1}$ is given to us. In this case we employ two different time-deformed
tangle machines, drawn in Figure 20, which represent the following
computations:

(4.15a)
$O_{1}(t)=(H_{0}\triangleright_{1}H_{\clubsuit})\triangleright_{0}H_{1}\enspace\;$
(4.15b)
$O_{1}^{\prime}(t)=(H_{0}\triangleright_{1}H_{1})\triangleright_{0}(H_{\clubsuit}\triangleright_{1}H_{1})\enspace.$

Figure 20. Equivalent computations.

In another round of experiments we embed $H_{1}$ into the tangle machine.
Hence, instead of using the expression for $H_{1}$ in (4.12), we consider
$H_{1}$ to be computed during the evolution of the system. In other words, we
let:

(4.16)
$G(t)=\left[(1-P_{z}^{4})\triangleright_{\star}(1-P_{z}^{2}(1-P_{z})^{2})\right]\triangleright_{\star}\left[(1-(1-P_{z})^{2}P_{z}^{2})\triangleright_{\star}(1-(1-P_{z})^{4})\right]\enspace,$

where $a\triangleright_{\star}b\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}(1-\frac{1}{2}t)a+\frac{1}{2}tb$. Note that indeed

$\lim_{t\to 1}G(t)=H_{1}\enspace.$

Substituting $H_{1}$ with its evolving version $G(t)$ in (4.15) yields

(4.17a)
$O_{1}(t)=(H_{0}\triangleright_{1}H_{\clubsuit})\triangleright_{0}G(t)\enspace\;$
(4.17b)
$O_{1}^{\prime}(t)=(H_{0}\triangleright_{1}G(t))\triangleright_{0}(H_{\clubsuit}\triangleright_{1}G(t))\enspace.$

The diagrams describing the two computations are shown in Figure 21. The
dashed region represents the logic underlying $G(t)$. Note that the number of
inputs/outputs of this _submachine_ corresponds to the number of conjunctive
clauses in the original DNF (4.9).

Figure 21. Equivalent computations in which the problem Hamiltonian logic is
encoded within the tangle (boxed region).

Figure 22 shows the energy gap over time for the various modes of computation
in this example. Here we use $\alpha=0.5$.

Figure 22. Energy gaps in the qudit example. Standard AQC using $H_{1}$ (thin
blue), standard AQC using $G(t)$ (green), time-deformed AQC using $H_{1}$
(purple), time-deformed AQC $O_{1}(t)$ using $G(t)$ (red), time-deformed AQC
$O_{1}^{\prime}(t)$ using $G(t)$ (black).

##  5\. Utility of tangle machines

In this paper we have introduced tangle machines and they have told us tales
of information flow in networks in both classical and quantum settings. In
what way can this distributive structure be of use to information theorists
and to computer scientists? We present two advantages that such a topological
description provides following [14] and [10].

###  5.1. Topological invariants

Knot diagrams are planar projections of knots in $\mathds{R}^{3}$ equipped
with over/under information. Knots in $3$–space are ambient isotopic if and
only if any two diagrams that represent them are related by a finite sequence
of Reidemeister moves. Is there an analogous topological interpretation for
tangle machines?

We have shown that tangle machines arise as planar projections of objects we
call _inca foams_ [14], that are necklaces of spheres glued together along
disjoint discs, all jointly embedded in $\mathds{R}^{4}$. Two inca foams are
ambient isotopic if and only if any two tangle machines which represent them
are related by a finite sequence of Reidemeister moves. This topological
interpretation provides us tools to construct and to study _topological
invariants_ of tangle machines, that are characteristic quantities which
coincide when tangle machines are equivalent. These will ideally have clear
and compelling interpretations in terms of information. We mention two
invariants.

Figure 23.  An Inca foam and a tangle machine representing it.

Shannon capacity:

There is a well-defined notion of _Shannon capacity_ for a graph which
measures the Shannon capacity of an communications channel defined by the
graph (e.g. [19]). This notion extends to tangle machines [14].

Define an assignment of colours to arcs of a tangle machine $M$ to be
_confusable_ is there is one of these colours that is uniquely determined by
the others. Let $\textrm{Cap}_{k}(M)$ denote the number of distinct assigments
of $k$ colours to arcs of $M$ which $M$ admits. Now define:

(5.1) $\mathrm{Cap}(M)\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}\sup_{k\in\mathds{N}}\sqrt[k]{\mathrm{Cap}_{k}(M)}$

Complexity:

Knots admit a binary operation called _connect sum_ under which they form a
commutative monoid:

$=$

A

B

Figure 24.  Machine 24A has complexity $1$. Machine 24B has complexity $2$ if
the horizontal strands are the same colour, otherwise it too has complexity
$1$.

Coloured knots also form a commutative monoid under the connect-sum operation
[34]. Although many related diagrammatic algebraic structures do not [31, 32],
tangle machines also form a commutative monoid under the connect-sum operation
[14]. More generally, we may define two submachines as being _independent_ if
they are connected along a set of arcs all of which share the same colour
[11]. The maximal number of nontrivial connect-summands is a topological
invariant of tangle machines, and is a (rough) measure of tangle machine
complexity. See Figure 24.

###  5.2. Flexibility of description

A second advantage of the tangle machine formalism is that, unlike directed
graphs, it is flexible. Reidemeister moves give different machines
representing different information flows which globally achieve the same task.

In Section 4 we will give examples in which the performance of one machine is
significantly better than the performance of an equivalent machine although
both achieve the same task. Further examples are in [13]. Here, following
[10], we shall present an idea for an application of the tangle machine
description to fault tolerance of sensor networks which perform fusion using
covariance intersection.

We may imagine a realization of a tangle machine using with modular robots
called ‘cubelets’ as shown in Figure 25.

Figure 25.  The R3 move realized using cubelets [18]. Both these networks have
the same outputs and thus represent different realizations of essentially the
same modular robot. The cubelets themselves do not move, and what changes is
only the configuration of which cubelet sends its output to which other
cubelet.

Three transmitting devices continuously stream data $x(T)$, $y(T)$, and
$z(T)$. Our task is to combine these data streams, eliminating redundancy
(e.g. because of the Problem of Double Counting [26]). Two schemes to combine
the data streams at a fixed time $T\geq 0$ are represented by the left and the
right hand side of the R3 move in Figure 12.

In the left machine, combine $x(T)$ and $y(T)$ with $z(T)$ with parameter
$t\in(0,1)$ to obtain fused data streams $x(T)\triangleright_{t}z(T)$ and
$y(T)\triangleright_{t}z(T)$. Assume that all estimators are Gaussian and that
the fusion is performed using covariance intersection. We read the fusion from
bottom to top because the overcrossing arc is directed from left to right. If
it were oriented from right to left, we would read from top to bottom and we
would be filtering out the data stream $z(T)$ from
$x(T)\triangleright_{t}z(T)$ and from $y(T)\triangleright_{t}z(T)$. On the
right, $x(T)\triangleright_{t}z(T)$ is combined with
$y(T)\triangleright_{t}z(T)$ using a weight $s\in(0,1)$.

The left and the right machine describe equivalent data stream fusion schemes,
which is visually indicated by the fact that the diagrams are related by
sliding one overcrossing arc over another. Indeed, the result of the data
stream fusion in the right machine is
$\left(x(T)\triangleright_{s}y(T)\right)\triangleright_{t}z(T)$, which is the
same combined data stream as in the left machine because redundant double
appearance of $z(T)$ in $x(T)\triangleright_{t}z(T)$ and
$y(T)\triangleright_{t}z(T)$ is eliminated by $\triangleright_{s}$ by
assumption.

However, there is an important difference between these two schemes on the
left and right of the R3 move. Imagine at some time $T_{1}>0$ that stream $y$
becomes faulty. In this case the left machine is superior because it contains
the intermediate data stream $x(T)\triangleright_{t}z(T)$ which might be
useful even when
$\left(x(T)\triangleright_{t}z(T)\right)\triangleright_{s}\left(y(T)\triangleright_{t}z(T)\right)$
is junk. Conversely, if $z$ becomes faulty at some time $T_{2}>0$ then the
right machine would be preferred. The top overcrossing arc might slide back
and forth at different times. Thus the machines involved in the R3 move might
be describing the underlying logic of a simple fault-tolerant data stream
fusion network.

A more general version of the same scheme is described in Figure 26. Consider
the network illustrated in the upper left corner of Figure 26. This network
has a set of outputs outside the bounding disk (not shown). Some set of
intermediate edges lies inside the subnetwork designated by $N_{L}$ and
represented as an empty circle. In the course of network operation, erroneous
streams of data cause one or more of the edges $0$,$1$, and $2$, to carry
faulty pieces of information, e.g. biased, inconsistent and otherwise
unreliable estimates. This is detected inside the network. To inhibit the
influence of this contamination on edges within $N_{L}$, the network performs
Reidemeister moves on itself, transforming itself into an equivalent network.
This is achieved by ‘sliding’ the faulty edges all the way over $N_{L}$, by
repeated application of the second and third Reidemeister moves. In the
resulting topology, the faulty edges have no effect on $N_{L}$, and so local
costs are improved.

Figure 26. Topological fault-tolerance. Switching between equivalent networks
ameliorate the effects of faults. The fault code appearing above each network
should be read as follows. The digits from left to right correspond to edges
$2$,$1$ and $0$. An “X” in the place of the $i$th digit signifies faulty
content in its respective edge.

In the above example, things were as easy as sliding faulty edges forward, but
this is only because the networks we considered are topologically
uninteresting. In the general case an optimal configuration may be difficult
to identify.

##  6\. To learn a tangle machine

Let’s now try a different way to connect tangle machines to the real world.
Given a data set we may ask whether there exists a tangle machine which
adequately the flow of information such a set. Can a tangle machine represent
a data-generating process for real world-data?

In this section we identify an interaction within real world data. It may be
possible to expand our method and to adapt existing causality-detection
algorithms to construct tangle machines from data.

###  6.1. Bayesian networks and Granger causality

One autoregressive system $X=\\{X(t)\,\mid t\in\mathds{N}\\}$ _Granger causes_
another autoregressive system $Y=\\{Y(t)\,\mid t\in\mathds{N}\\}$ if lagged
values $\mathcal{L}^{T-p:T-1}(X)=(X(T-1),X(T-2),\ldots,X(T-p))$ contain
information about $Y_{T}$ beyond the information contained in past values of
$Y$ itself for some fixed $p\in\mathds{N}$ and for all $T>p$. Magnitude of
Granger causality is measured a quantity called the _transfer entropy_ from
$X$ to $Y$.

A Bayesian network is a directed acyclic graph whose nodes represent random
variables and whose edges represent conditional dependencies. Generalizing,
nodes of Bayesian networks may represent autoregressive systems and edges may
represent transfer entropies from the tail to the head of each edge [36]. Thus
the tail of an edge Granger causes its head. There is a well-developed family
of algorithms to learn transfer entropies for a given Bayesian network from
time-series data.

We consider an interaction with a single input patient as representing a
triangular Bayesian network. The agent corresponds to the source in the
network, and the two patients correspond to the remaining two nodes. Thus, our
idea is that the agent Granger causes both patients. See Figure 27.

Our model is:

(6.1) $\begin{array}[]{l}Z_{k+1}=s_{X\to Z}\mathcal{L}^{k-p:k-1}(X)+s_{Y\to
Z}\mathcal{L}^{k-p:k-1}(Y)+\nu_{Z}\\\ X_{k+1}=s_{Z\to
X}\mathcal{L}^{k-p:k-1}(Z)+s_{Y\to X}\mathcal{L}^{k-p:k-1}(Y)+\nu_{X}\\\
Y_{k+1}=s_{X\to Y}\mathcal{L}^{k-p:k-1}(X)+s_{Z\to
Y}\mathcal{L}^{k-p:k-1}(Z)+\nu_{Y}\enspace,\end{array}$

where all variables are assumed to be normally distributed, $s$ terms are
constant, and $\nu$ terms are noise.

Under the above assumptions, a short computation shows that the expression for
the transfer entropies is maximized when the $s$ parameters are maximal [9].

Thus to maximize the transfer entropy for a given data set, our goal becomes
to solve the following least-square problem to estimate the $s$ parameters:

(6.2) $\begin{array}[]{l}Z_{k+1}=s_{X\to Z}\mathcal{L}^{k-p:k-1}(X)+s_{Y\to
Z}\mathcal{L}^{k-p:k-1}(Y)\\\ X_{k+1}=s_{Z\to
X}\mathcal{L}^{k-p:k-1}(Z)+s_{Y\to X}\mathcal{L}^{k-p:k-1}(Y)\\\
Y_{k+1}=s_{X\to Y}\mathcal{L}^{k-p:k-1}(X)+s_{Z\to
Y}\mathcal{L}^{k-p:k-1}(Z)\enspace.\end{array}$

We then choose the configuration that corresponds to the greater value among
each pair of parameters $\\{s_{X\to Y},s_{Y\to X}\\}$, $\\{s_{X\to Z},s_{Z\to
X}\\}$, and $\\{s_{Z\to Y},s_{Y\to Z}\\}$. This process fits a single input-
patient interaction to a triangular Bayesian network.

By extension, an interaction with agent $Y$, input patients
$X_{1},X_{2},\ldots,X_{k}$, and output patients $Z_{1},Z_{2},\ldots,Z_{k}$
with $Z_{i}=X_{i}\triangleright_{\omega}Y$ corresponds to a Bayesian network
with nodes $Y,X_{1},X_{2},\ldots,X_{k},Z_{1},Z_{2},\ldots Z_{k}$ in which the
$X_{i}^{\prime}s$ arise as mixtures of autoregressive processes such that $Y$
only acts on one of these and is independent of the others. The extension of
our method to these and to more complicated Bayesian networks will be
considered in future work.

Figure 27.  An interactions and its Bayesian network analogue. The arrow
between $Y$ and $Z$ may point either way. An interaction-learning algorithm
should learn the correct network configuration. Thus it should learn which the
agent is, and the quandle operation.

We present an example in which we have learnt an interaction from real-life
search data. Around 2006, the field of signal processing was revolutionized by
the appearance of the concept of _compressed sensing_. Compressed sensing
recovers signals using far fewer observations than required by the
Shannon–Nyquist sampling theorem. Several people were involved, one of whom
was Emmanuel Candes. This story may be described by an interaction of the
form: E. Candes _causes_ a shift of state from _Shannon–Nyquist sampling_ to
_compressed sensing_.

We used _Google Trends_ to generate time-series data of hits per year from
2000 to 2010 for the three search terms: E. Candes, Shannon--Nyquist sampling,
and compressed sensing. We then used the filtering-based detection algorithm
described in [9] to recover the underlying Bayesian network. As shown in
Figure 28, the actual relationship between the time-series could be recovered
up to a time order of Shannon--Nyquist sampling and compressed sensing. There
was an ambiguity between two possible interactions both of which identify E.
Candes as a cause of the paradigm shift.

A refined and expanded version of this method will be needed to detect
machines with more than one interaction.

Figure 28. Detecting an interaction from time-series data. Colour code: Red =
E. Candes, Blue = Shannon--Nyquist sampling, Green = compressed sensing. The
Bell-curves show the statistical significance of determining the corresponding
arrow direction. Roughly, the further apart the curves are for each arrow the
more significant is its (causal) direction.

## References

  * [1] Abramsky S. & Coecke, B. 2009 Categorical quantum mechanics.  In _Handbook of Quantum Logic and Quantum Structures_ , Vol. 2, 261–323.  arXiv:0808.1023
  * [2] Aharonov, D. & Van Dam, W. & Kempe, J. & Landau, Z. & Lloyd, S. & Regev, O. 2008 Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation.  _SIAM Review_ 50(4), 755–787.
  * [3] Amari, S. & Nagaoka, H. 2007 Methods of information geometry.  Translations of Mathematical Monographs (Vol. 191), American Mathematical Soc.
  * [4] Baez, J. & Stay, M. 2011 Physics, topology, logic and computation: A Rosetta stone.  In _New Structures for Physics_ , Lecture Notes in Phys. 813, 95–172.  arXiv:0903.0340
  * [5] Bohl, M. & Rynn, M. 2007 Tools for Structured and Object-Oriented Design.  Prentice Hall, Upper Saddle River, NJ, USA.
  * [6] Buliga, M. 2011 Braided spaces with dilations and sub-riemannian symmetric spaces.  In _Geometry. Exploratory Workshop on Differential Geometry and its Applications_ , (D. Andrica & S. Moroianu Ed.), Cluj-Napoca 21–35.  arXiv:1005.5031
  * [7] Buliga, M. 2011 Computing with space: A tangle formalism for chora and difference.  Preprint.  arXiv:1103.6007
  * [8] Buliga, M. & Kauffman, L. 2014 Chemlambda, universality and self-multiplication.  In _ALIFE 14: Proceedings of the Fourteenth International Conference on the Synthesis and Simulation of Living Systems_ , 490–497.  arXiv:1403.8046
  * [9] Carmi, A. 2013 Compressive system identification: sequential methods and entropy bounds.  _Digit. Signal Process._ 23(3), 751–770.
  * [10] Carmi, A.Y. & Moskovich, D. 2014 Low dimensional topology for information fusion.  In _BICT14: Proceedings of the 8th International Conference on Bio-inspired Information and Communications Technologies_ , ACM/EAI, 251–258.  arXiv:1409.5505
  * [11] Carmi, A.Y. & Moskovich, D. 2014 Tangle Machines II: Invariants.  arXiv:1404.2863
  * [12] Carmi, A.Y. & Moskovich, D. 2015 Computing with coloured tangles.  _Symmetry_ 7(3), 1289–1332.  arXiv:1408.2685
  * [13] Carmi, A.Y. & Moskovich, D. 2015 Tangle machines.  _Proc. R. Soc. A_ 471, 20150111.  Conference version: Calude, C.S., Dinneen, M.J. (eds.) UCNC 2015, LNCS, vol. 9252, 277– 289. Springer, Heidelberg.  arXiv:1404.2862
  * [14] Carmi, A.Y. & Moskovich, D. 2015 Inca foams.  arXiv:1509.01284
  * [15] Chang, K.C., Chong, C.-Y. & Mori, S. 2010 Analytical and Computational Evaluation of Scalable Distributed Fusion Algorithms.  _IEEE Transactions on Aerospace and Electronic Systems_ 46(4), 2022–2034.
  * [16] Chen, L. & Arambel, P.O. & Mehra, R.K. 2002 Estimation under unknown correlation: Covariance intersection revisited.  _IEEE T. Automat. Contr._ 47(11), 1879–1882.
  * [17] Clark, D. & Morrison, S. & Walker, K. 2009 Fixing the functoriality of Khovanov homology.  _Geom. Topol._ 13(3), 1499–1582.
  * [18] Cubelets Robot Construction for Kids — Modular Robotics.  Retrieved from http://www.modrobotics.com/cubelets/
  * [19] Erickson, M.J. 2014 Introduction to Combinatorics.  Discrete Mathematics and Optimization 78 (2nd ed.). John Wiley & Sons.
  * [20] Farhi, E. & Goldstone, J. & Gutmann, S. & Sipser, M. 2000 Quantum computation by adiabatic evolution.  arXiv:quant-ph/0001106
  * [21] Farhi, E. & Goldstone, J. & Gutmann, S. 2002 Quantum adiabatic evolution algorithms with different paths.  arXiv:quant-ph/0208135
  * [22] Farhi, E. & Goldstone, J. & Gosset, D. & Gutmann, S. & Meyer, H.B. & Shor, P. 2011 Quantum Adiabatic Algorithms, Small Gaps, and Different Paths.  _Quantum Information & Computation_ 11(3–4), 181–214.  arXiv:0909.4766
  * [23] Fox, R.H. 1961 A quick trip through knot theory.  in: _Topology of 3-Manifolds and Related Topics_ , M.K. Fort (Ed.), Prentice-Hall, NJ, 120–167.
  * [24] Franken, D. & Hupper, A. 2005 Improved fast covariance intersection for distributed data fusion.  In _Proceedings of the 8th International Conference on Information Fusion_.
  * [25] Ishii, A., Iwakiri, M., Jang, Y. & Oshiro, K. 2013 A $G$–family of quandles and handlebody-knots.  _Illinois J. Math._ , 57 817–838.  arXiv:1205.1855
  * [26] Jazwinski, A.H. 1970 Stochastic Processes and Filtering Theory.  New York: Academic Press.
  * [27] Joyce, D. 1982 A classifying invariant of knots: The knot quandle.  _J. Pure Appl. Algebra_ 23, 37–65.
  * [28] Julier, S. Uhlmann, J.K. 2001 General decentralized data fusion with covariance intersection.  In _Handbook of Multisensor Data Fusion_ , CRC Press, Boca Raton, FL.
  * [29] Kauffman, L.H. 1994 Knot automata.  In _Twenty-Fourth International Symposium on Multiple-Valued Logic, Conference Proceedings_ , May 25-27 1994, Boston, Massachusetts, IEEE Computer Society Press, 328–333.
  * [30] Kauffman, L.H. 1995 Knot logic.  In _Knots and Applications_ (ed L. Kauffman), Series of Knots and Everything 6, World Scientific Publications, 1–110.
  * [31] S.G. Kim, Virtual knot groups and their peripheral structure,  _J. Knot Theory Ramifications_ 9(6) (2000) 797–812.
  * [32] T. Kishino and S. Satoh, A note on non-classical virtual knots,  _J. Knot Theory Ramifications_ 13(7) (2004) 845–856.
  * [33] Knuth, K.H. 2015 The Deeper Roles of Mathematics in Physical Laws.  Third place, FQXi essay contest: “2015 Trick or Truth: The mysterious connection between physics and mathematics.”  Retrieved from http://fqxi.org/data/essay-contest-files/Knuth_knuth---fqxi-essay---.pdf
  * [34] Moskovich, D. 2006 Surgery untying of coloured knots.  _Algebr. Geom. Topol._ 6, 673–697.  `arXiv:math.GT/0506541`
  * [35] Niehsen, W. 2002 Information fusion based on fast covariance intersection filtering.  in _Proceedings of the Fifth International Conference on Information Fusion, 2002_ 2(2), 901–904.
  * [36] Pearl, J. 2009 _Causality: Models, reasoning, and inference._ 2nd edn. Cambridge University Press.
  * [37] Przytycki, J.H. 2011 Distributivity versus associativity in the homology theory of algebraic structures.  _Demonstration Mathematica_ 44(4), 823–869.  arXiv:1109.4850
  * [38] Tietze, H.F.F. 1908 Über die topologische Invarianten mehrdimensionaler Mannigfaltigkeiten.  _Monatshefte für Mathematik und Physik_ 19 1–118.
  * [39] Vicary, J. 2012 Higher Semantics for Quantum Protocols.  In _Proceedings of the 27th Annual ACM/IEEE Symposium on Logic in Computer Science_ , 606–615.  arXiv:1207.4563

##  Appendix A Appendix

The proof of Proposition 2.1 is the combination of the following two lemmas
which are surely well-known.

######  Lemma A.1.

The covariance intersection of weight $\omega\in[0,1]$ of two unnormalized
Gaussian probability density functions $p(X)$ and $p(Y)$ is
$p(X)^{1-\omega}p(Y)^{\omega}$.

###### Proof.

Let $p(X),p(Y)$ be unnormalized Gaussian densities parameterized by their mean
and covariance, $(\hat{X},C_{X})$ and $(\hat{Y},C_{Y})$, respectively. The pdf
$p(X)^{1-\omega}p(Y)^{\omega}$ is given by the expression:

(A.1)
$\exp\left(-\frac{1}{2}\left[(1-\omega)(Z-\hat{X})^{T}C_{X}^{-1}(Z-\hat{X})+\omega(Z-\hat{Y})^{T}C_{Y}^{-1}(Z-\hat{Y})\right]\right)\enspace.$

We verify that this expression equals:

(A.2)
$\exp\left(-\frac{1}{2}(Z-\hat{Z})^{T}C_{Z}^{-1}(Z-\hat{Z})\right)\enspace,$

for:

(A.3a) $\hat{Z}=(1-\omega)C_{Z}C_{X}^{-1}\hat{X}+\omega
C_{Z}C_{Y}^{-1}\hat{Y}\enspace\;$ (A.3b)
$C_{Z}^{-1}=(1-\omega)C_{X}^{-1}+\omega C_{Y}^{-1}\enspace.$

We compute that $C_{X}^{-1}=-\frac{\partial^{2}\log p(x)}{\mathop{\partial
x}\mathop{\partial x}^{T}}$ which is called the _precision matrix_ of $p(X)$.
In particular,

(A.4) $C_{Z}^{-1}=-\frac{\partial^{2}\log p(z)}{\mathop{\partial
z}\mathop{\partial z}^{T}}=(1-\omega)\,C_{x}^{-1}+\omega\,C_{Y}^{-1}\enspace,$

which follows from (A.1).

The mode $\hat{X}$ satisfies:

(A.5) $\left.\frac{\partial\log p(x)}{\partial
x}\right|_{x=\hat{X}}=0\enspace.$

The mode $\hat{Z}$ of $p(Z)$ is thus obtained from (A.1) by

(A.6) $2\left.\frac{\partial\log p(z)}{\partial
z}\right|_{z=\hat{Z}}=(1-\omega)\,C_{x}^{-1}(\hat{Z}-\hat{X})+\omega\,C_{Y}^{-1}(\hat{Z}-\hat{Y})=0\enspace,$

finally giving

(A.7) $C_{z}^{-1}\hat{Z}=(1-\omega)C_{x}^{-1}\hat{X}+\omega
C_{Y}^{-1}\hat{Y}\enspace.$

∎

######  Lemma A.2.

Let $P$ be a space of probability density functions (pdfs) over some domain.
Consider the functional $J\colon\,P\to\mathds{R}$ defined by

(A.8) $J(g(X))\stackrel{{\scriptstyle\textup{\tiny
def}}}{{=}}(1-\omega)\mathrm{KL}\left(g(X)\|p(X)\right)+\omega\mathrm{KL}\left(g(X)\|q(X)\right)$

where $g(X)$, $p(X)$, and $q(X)$ are pdfs in $P$ and
$\mathrm{KL}(\cdot\|\cdot)$ is the Kullback–Leibler divergence. Then the
following holds for any $\omega\in[0,1]$ and $g(X)\in P$:

$J\left(\frac{p(x)^{1-\omega}q(x)^{\omega}}{\int_{x}p(x)^{1-\omega}q(x)^{\omega}\mathop{dx}}\right)\leq
J(g(X))\enspace.$

###### Proof.

Writing down the Kullback–Leibler divergence explicitly, we have:

(A.9)
$\min_{g(X)}J(g(X))=\min_{g(X)}\left[(1-\omega)\int_{x}g(x)\log\frac{g(x)}{p(x)}\mathop{dx}+\omega\int_{x}g(x)\log\frac{g(x)}{q(x)}\mathop{dx}\right]=\\\
=\min_{g(X)}\int_{x}g(x)\log\frac{g(x)}{p(x)^{1-\omega}q(x)^{\omega}}\mathop{dx}=\\\
=\min_{g(X)}\left[\int_{x}g(x)\log\frac{g(x)}{p(x)^{1-\omega}q(x)^{\omega}}\mathop{dx}+\int_{x}p(x)^{1-\omega}q(x)^{\omega}\mathop{dx}-\int_{x}p(x)^{1-\omega}q(x)^{\omega}\mathop{dx}\right]=\\\
=\min_{g(X)}\left[\mathrm{KL}\left(g(X)\bigg{\|}\frac{p(X)^{1-\omega}q(X)^{s}}{\int_{x}p(x)^{1-\omega}q(x)^{s}\mathop{dx}}\right)\right]-\int_{x}p(x)^{1-\omega}q(x)^{\omega}\mathop{dx}\enspace.$

But $\mathrm{KL}(\cdot\|\cdot)\geq 0$ vanishes if and only if its arguments
coincide, and the result follows. ∎