Creating and sharing knowledge for telecommunications

Topological Quantum Information, Khovanov Homology and the Jones Polynomial

on 30-11-2012

... Louis Kauffman (guest of CAMGSD), University of Illinois at Chicago

30/11/2012, 15:00 ­ Room P4.35, Mathematics Building, IST.

Topological Quantum Information, Khovanov Homology and the Jones Polynomial

In this talk we give a quantum statistical interpretation for the bracket polynomial state sum K and for the Jones polynomial. We use this quantum mechanical interpretation to give a new quantum algorithm for computing the Jones polynomial. This algorithm is useful for its conceptual simplicity, and it applies to all values of the polynomial variable that lie on the unit circle in the complex plane. Letting C(K) denote the Hilbert space for this model, there is a natural unitary transformation U from C(K) to itself such that K=tr(U). The quantum algorithm arises directly from this formula via the Hadamard Test. We then show that the framework for our quantum model for the bracket polynomial is a natural setting for Khovanov homology. The Hilbert space C(K) of our model has basis in one-to-one correspondence with the enhanced states of the bracket state summmation and is isomorphic with the chain complex for Khovanov homology with coefficients in the complex numbers. We show that for the Khovanov boundary operator d defined on C(K) we have the relationship dU+Ud=0. Consequently, the unitary operator U acts on the Khovanov homology, and we therefore obtain a direct relationship between Khovanov homology and this quantum algorithm for the Jones polynomial. The formula for the Jones polynomial as a graded Euler characteristic is now expressed in terms of the eigenvalues of U and the Euler characteristics of the eigenspaces of U in the homology. The quantum algorithm given here is inefficient, and so it remains an open problem to determine better quantum algorithms that involve both the Jones polynomial and the Khovanov homology. More Information..

On two-dimensional products of modal logics

on 23-11-2012

... Sérgio Marcelino, SQIG-IT

November 23, 2012, Friday, 16h15m.

Abstract: Products of Kripke frames are natural relational structures for modelling the interaction between different modal operators, representing notions such as time, space, knowledge, actions. The product construction shows up in various disguises in many logical formalisms, such as algebras of relations in algebraic logic, finite variable fragments of classical, intuitionistic and modal predicate logics, temporal-epistemic logics, dynamic topological logics, modal and temporal description logic.

It is known that n-products of modal logics have in general a very complex behaviour for n>2. For example, every logic between K×K×K and S5×S5×S5 is non finitely axiomatisable, and both its satisfiability and its finite-frame problem are undecidable. However, no such examples were known in the n=2 case. On the contrary, a big class of binary products of modal logics is known to be finitely axiomatisable, every 2-product of two Horn axiomatisable logics is in this class.

In this talk I will present some recent contributions to the understanding of this construction. In [1] the first examples of two-dimensional products of finitely axiomatisable modal logics that are not finitely axiomatisable were presented. If a modal logic L is finitely axiomatisable, then it is of course decidable whether a finite frame is a frame for L: one just has to check the finitely many axioms in it. If L is not finitely axiomatisable, then this might not be the case. In [2], is shown that the finite frame problem for the modal product logic K4.3×S5 is decidable. K4.3×S5 is outside the scope of both the known finite axiomatisation results, and the non-finite axiomatisability results of [1]. So, it is not known whether K4.3×S5 is finitely axiomatisable. We will discuss whether this result bring us any closer to either proving non-finite axiomatisability of K4.3×S5, or finding an explicit, possibly infinite, axiomatisation of it.

[1] A. Kurucz and S. Marcelino: Non-finitely axiomatisable two-dimensional modal logics, Journal of Symbolic Logic, vol. 77 (2012).
[2] A. Kurucz and S. Marcelino: Finite frames for K4.3×S5 are decidable, Advances in Modal Logic, Volume 9, College Publications (2012).

Room: 3.10, Mathematics

Support: SQIG/Instituto de Telecomunicações with support from FCT and FEDER namely by the FCT project PEst-OE/EEI/LA0008/2011.
More Information..