### Embarking on Logic: Gentle Reading on Doering & Coecke’s articles

06Aug13

Resurrecting this blog for my research interests. Lately, I’m back on reading materials on logic for quantum theory in the hope for initiating a new research direction in view of pending collaborative project with University of Auckland. My usual scanning of materials include following developments made by certain researchers working in the topics I’m interested in. In this post, I look to Andreas Doering’s “Some Remarks on the Logic of Quantum Gravity” (arXiv:1306.3076) and Bob Coecke’s “An Alternative Gospel of Structure: Order, Composition, Processes” (arXiv: 1307.4038); these two have the benefit of being less technical to mathematically informed readers. Both authors, I had the pleasure and honour of inviting to our institute and meeting them personally. Both also approach quantum theory from a category-theoretic point of view. Category theory is a relatively new tool picked up theoretical physicists and is considered hard to learn and will take time to get used to. For a gentle introduction to category theory, one can refer to the book by F.W. Lawvere & S.H. Schanuel, “Conceptual Mathematics – A First Introduction to Categories” (Cambridge University Press, 2005). Bob has his own introductory article to categories (with Eric Oliver Paquette), “Categories for the Practising Physicist” that would connect straight to his graphical approach. I should also point out to interested readers to the book by Robert Geroch, “Mathematical Physics” (Univ. of Chicago Press, 1985) that frames usual tools of theoretical physicists within the category-theoretic viewpoint.

Andreas Doering is a collaborator of Chris Isham whom I follow very much since the early days of quantum gravity. Doering’s artcile is said to be prompted by Isham’s question on how to judge a given theory of quantum gravity. As the title of the article said, it is not about quantum gravity but its underlying logic. The point is that the current framework of quantum theory is largely instrumentalist in nature with measurement playing a key role. The argument here is that to take an instrumentalist viewpoint may not be suitable for quantum gravity. First, quantum gravity is supposed to describe the whole universe and thus to have an external observer performing measurements on it will be awkward. It would thus be natural to look for a formalism that does not necessitate the idea of measurement. Second, measurement requires a background space-time which ought to be treated as quantum objects in quantum gravity. This more or less forces a realist stance for the theory of quantum gravity. The article made the following maxim:

The mathematical apparatus of a future theory of quantum gravity should not be based on Hilbert spaces and hence should not be a quantum theory in the standard sense.

Isham had already of course proposed a topos-theoretic reformalism of quantum theory as a neo-realistic approach in a series of papers with collaborators Jeremy Butterfield, John Hamilton and Doering. Isham’s general views can be read from his articles, “Some Possible Roles of Topos Theory in Quantum Theory and Quantum Gravity“, Found. Phys. 30 (2000) 1707-1735 (with J. Butterfield); “Some Reflections on the Status of Conventional Quantum Theory When Applied to Quantum Gravity” (arXiv: quant-ph/0206090); and “Topos Method in the Foundations of Physics” (arXiv: 1004.3564), appeared in H. Halvorson (ed), Deep Beauty – Understanding the Quantum World Through Mathematical Innovations, (Cambridge Univ. Press, 2011). The idea is to replace the use of assumed continuum of complex (real) numbers in quantum theory (for space-time) by something general but yet preserve some desirable properties of realism as found in classical theories (hence a realist formalism of quantum theory).

In classical theories, they are very much based on sets in the form of say state spaces $\mathcal{S}$. Physical quantities, say of $A$ are thus maps $f_A:\mathcal{S}\rightarrow\mathbb{R}$. The availability of real number assignments to physical quantities are essentially the makes of realism in classical theories. Propositions like $A\epsilon\Delta\subset\mathbb{R}$ can be easily traced back to a set of states $f_a^{-1}(\Delta)$. Thus, in classical physics, one can build proposition algebra $\mathcal{P}(\mathcal{S})$, which is a Boolean algebra, based on state space $\mathcal{S}$. Points $s\in\mathcal{S}$ can now be assigned true or false, $t_s:\mathcal{P}(\mathcal{S}) \rightarrow (\textrm{true},\textrm{false})$ i.e.

$t_s: X \mapsto \begin{cases} \textrm{true}\ &\textrm{if}\ s\in X\\ \textrm{false}\ &\textrm{if}\ s\not\in X \end{cases}$.

In quantum theory, such assignments are obstructed due to Kochen-Specker theorem. This obstruction can be overcome if we relax some assumptions

• Have a weaker structure than Boolean algebra;
• Have more truth values beyond true or false;
• Use more general maps than Boolean algebra and use morphisms as states.

If one can have truth values for all states, then one can claim a neo-realist interpretation. This is essentially what is being done in the topos approach. States are being replaced by state objects carried by spectral presheaves which are varying sets $\underline{\Sigma}$ over von Neumann algebra $\mathcal{V}(\mathcal{N})$ (won’t go into details here) and truth values are carried by value presheaves $\underline{\mathbb{R}}^\leftrightarrow$ (unsharp values). THe spectral presheaves are associated to the topos $\textrm{Set}^{{\mathcal{V}(\mathcal{N})}^{\textrm{op}}}$ which has an internal logic structure. Subpresheaves of $\textrm{Set}^{{\mathcal{V}(\mathcal{N})}^{\textrm{op}}}$ forms a Heyting algebra, which is a bounded lattice with largest element $1$ and smallest element $0$ and a binary operation $\Rightarrow$ such that

• $a\Rightarrow a = 1$;
• $a\wedge (a\Rightarrow b) = a\wedge b$;
• $b\wedge (a\Rightarrow b) = b$;
• $a\Rightarrow (b\wedge c) = (a\Rightarrow b)\wedge (a\Rightarrow c)$.

The algebra obeys the distributive law $a\wedge (b\vee c)= (a\vee b)\wedge (a\vee c)$ (unlike the earlier quantum logic attempts). Unlike Boolean algebra, it has a distinguishing property with the negation operation $\neg$. It shares the following conjunction relation with Boolean algebra:

$a\wedge\neg a = 0$;

but it differs on the disjunction relation:

$a\vee\neg a \neq 1$,

i.e. the law of excluded middle does not hold. It is noted in this sort of logical systems that proofs by contradiction are not available. Presently, this topos approach is still in progress in reconstructing quantum theory and is still too early to see its implications.

Moving on to Coecke’s article; while it addresses quantum foundations, Coecke’s approach does not put realism as its main goal but rather he propounds the use of a higher-level language and viewpoint of interactionism or processes for quantum theory. His viewpoint on the logic of quantum theory is best read from his article “The Logic of Quantum Mechanics – Take II” (arXiv: 1204.3458), and “Compositional Quantum Logic” (arXiv: 1302.4900) (with Chris Heunen and Aleks Kissinger) that puts the conventional quantum logic into a larger perspective. One should also check out the articles “Kindergarten Quantum Mechanics” (arXiv: quant-ph/0510032) and “Quantum Picturalism” (arXiv: 0908.1787) for introduction to the diagrammatic approach of Coecke. The present-discussed article however goes beyond quantum theory.and aims to highlight fundamental mathematical structures that eventually underlie quantum theory and various other applications such as computer science and linguistics. They are ordering, composability (of things), and processes composable in time.

We are probably familiar with ordering through real numbers (as a complete ordered field) or its subsets but it can be extended beyond numbers. A total ordering on the set $X$ is a relation $\leq$ such that for all $x,y,z\in X$:

• $x\leq y,\ y\leq x\quad\Rightarrow\quad x=y$ (anti-symmetric)
• $x\leq y,\ y\leq z\quad\Rightarrow\quad x\leq z$ (transitivity)
• $x\leq y\ \textrm{or}\ y\leq x$ (total)

There are weaker structures than total order namely

• preordering on $X$ is a transitive relation $\lesssim$ which is reflexive i.e. $\forall x\in X,\ x\lesssim x$;
• partial ordering on $X$ is an anti-symmetric preordering $\leq$ (without totality).

An example of preordering is majorization preordering on probabilities, which has applications in quantum information (will not go into details). The partial ordering being richer has more to offer. One can define an implication connective $\Rightarrow : X\times X\rightarrow X$ on partial ordering $X$ through the law of $\wedge$-residuation:

$(a\wedge b)\leq c\quad\textrm{if and only if}\quad a\leq (b\Rightarrow c)$.

Such partial orderings in fact gives Heyting algebra mentioned earlier.The case of Boolean algebra is a special case of implication, for which $a\Rightarrow b :=\not a\vee b$ (their equivalence can be seen in their truth tables often taught in courses of logic). This connects us back to the logics mentioned earlier and in particular to algebraic proof theory for which a preordering $a\lesssim b$ is equivalent to the statement from $a$, we can prove $b$. Generally we can associate preordering with the ability to process $a$ into $b$ and thus the various applications shown in the table given by Coecke:

The other structure that is considered fundamental is the ability to compose things. This is captured by the mathematical structure of a monoid which is a set $X$ with an associative binary operation $\cdot : X\times X\rightarrow X$ with a two-sided unit $1\in X$ i.e.

• $\forall\ x,y,z\in X:\ x\cdot (y\cdot z) = (x\cdot y)\cdot z$;
• $\forall\ x\in X:\ 1\cdot x= x\cdot 1=x$.

The monoid can be equipped with a total/partial/pre-order to give totally/partially/pre-ordered monoid which in addition satisfies monotonicity of monoid multiplication

• $\forall\ x,y,x',y'\in X:\ x\lesssim y,\ x'\lesssim y'\quad\Rightarrow\quad x\cdot x'\lesssim y\cdot y'$.

Essentially, there are two forms are composabilities that one needs namely

• Composition of things or parallel composition – often considered commutative
• Composition of processes or sequential composition – generally non-commutative

The final structure is to make explicit the processes with composability and this is done by introducing strict symmetric monoidal category $\mathcal{S}$ which is

• a collection of things/systems $\vert\mathcal{S}\vert$,
• with a monoid structure $(S,\otimes.1)$,

and for each pair $S,S' \in \vert\mathcal{S}\vert$,

• a collection of processes $\mathcal{S}(S,S')$

with two unital associative composition structures

• $\forall\ S,S',S''\in\vert\mathcal{S}\vert,\ (-\circ -):\ \mathcal{S}(S,S')\times\mathcal{S}(S',S'')\rightarrow\mathcal{S}(S,S'')$,
• $\forall\ S,S',S'',S'''\in\vert\mathcal{S}\vert,\ (-\circ -):\ \mathcal{S}(S,S')\times\mathcal{S}(S'',S''')\rightarrow \mathcal{S}(S\otimes S'',S'\otimes S''')$.

Now, all of these might be a bit intimidating but they are just what we need to produce a diagrammatic language that is intuitive.

Processes are given boxes with input and output wires:

Systems are carried by wires:

Composability of processes and things are given by the following diagrams:

Now, what happens in this language is that many identities become simpler. For instance, $(f'\circ f)\otimes(g'\circ g) = (f'\otimes g')\circ (f\otimes g)$ translates into the following diagram:

If one removes the bracket, the identity becomes a tautology. This shows the power of the diagrammatic language.

If one add further ingredients, one can see the applicability of this diagrammatic approach in quantum information, say the teleportation protocol:

in linguistics for the theory of meaning of sentences:

and in probability theory, say probabilistic Bayesian inference:

It will be interesting to see the development of this diagrammatic approach, to see how far it can be pushed. For now, one begin to see this taking the analogous intuitive role of Feynman diagrams in particle physics.