Invited Talks

Cem Say
Professor at Boğaziçi Üniversitesi, Turkey.

Energy Complexity of Computation
Computational complexity theory is the study of the fundamental resource requirements associated with the solutions of different problems. Time, space (memory) and randomness (number of coin tosses) are some of the resource types that have been examined both independently, and in terms of tradeoffs between each other, in this context. Since it is well known that each bit of information "forgotten" by a device is linked to an unavoidable increase in entropy and an associated energy cost, one can also view energy as a computational resource. Constant-memory machines that are only allowed to access their input strings in a single left-to-right pass provide a good framework for the study of energy complexity. There exists a natural hierarchy of regular languages based on energy complexity, with the class of reversible languages forming the lowest level. When the machines are allowed to make errors with small nonzero probability, some problems can be solved with lower energy cost. Tradeoffs between energy and other complexity measures can be studied in the framework of Turing machines or two-way finite automata, which can be rewritten to work reversibly if one increases their space and time usage.

Robin Kaarsgaard
Assistant Professor at The University of Southern Denmark, DK.

The Quantum Effect: A Recipe for Quantum Π
The prevalent view of quantum computing characterises it as an extension of reversible classical computing with constructs for managing superpositions. Adding native syntactic support for superpositions has disadvantages, however. It requires the addition of scalars with an associated algebra and imposes a low-level matrix-oriented perspective on the resulting model. We use free categorical constructions to characterise quantum computing as the combination of two copies of a reversible classical language, glued by the complementarity equations of classical structures. We apply this recipe to construct an approximately universal quantum programming language from two copies of Π, the classical language internal to rig groupoids. The construction takes the form of a series of arrows giving a positive answer to the question of the existence of a quantum effect, allowing the addition of measurement by layering a further effect on top, and permitting reasoning about quantum programs (with or without measurement) through a combination of classical reasoning and reasoning about complementarity.