Reversible Computation (RC)

July 18 - July 19, 2023, Giessen, Germany

# 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**

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.

**Important dates :**

Abstract submission:

February 6th, 2023

Submission deadline:

February 13, 2023

Notification to authors:

April 3, 2023

Final version:

April 24, 2023

Conference:

July 18 - July 19, 2023

**Program Chairs:**

Martin Kutrib

*Justus-Liebig-University Giessen, Germany*

Uwe Meyer

*Technische Hochschule Mittelhessen (University of Applied Sciences) Giessen, Germany*