Reversible Computation (RC)
July 18 - July 19, 2023, Giessen, Germany
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.
Postdoctoral Researcher at The University of Edinburgh, UK.
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.
February 6th, 2023
February 13, 2023
Notification to authors:
April 3, 2023
April 24, 2023
July 18 - July 19, 2023
Justus-Liebig-University Giessen, Germany
Technische Hochschule Mittelhessen (University of Applied Sciences) Giessen, Germany