BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Playing Reversible Pebble Games for Quantum Memory Management
DTSTART;VALUE=DATE-TIME:20191119T161500
DTEND;VALUE=DATE-TIME:20191119T170000
DTSTAMP;VALUE=DATE-TIME:20240525T215520Z
UID:84fc7f846eb1c990ab2d4bac571c6f056b612d9c07f84971450cc123
CATEGORIES:Conferences - Seminars
DESCRIPTION:Mathias Soeken works as a research design engineer at Microsof
t and as a researcher at the EPFL in Lausanne\, Switzerland. From 2009 to
2015 he worked at the University of Bremen\, Germany and has been a regula
rly visiting post doc at UC Berkeley\, CA\, USA in the group of Robert K.
Brayton. He holds a Ph.D. degree (Dr.-Ing.) in Computer Science from Unive
rsity of Bremen\, Germany (2013). His research interests are logic synthes
is\, quantum computing\, reversible logic\, and formal verification. Mathi
as Soeken is member of the IEEE and of the ACM.\nThe reversible pebble gam
e is played on a connected directed acyclic graph with marked vertices. St
arting from an initial configuration in which all vertices are unmarked\,
the goal of the game is to reach a configuration in which a given subset o
f vertices is marked\, but none of the vertices outside of the subset are
marked. Two rules govern the dynamics of the game: i) one can perform a mo
ve by marking or unmarking a vertex\, if and only if all its ingoing adjac
ent vertices are marked\; and ii) the number of marked vertices is bounded
to some constant P. The question is whether there exists a solution to th
e game with P pebbles\, and if so how many moves are required to reach the
goal configuration. In the talk\, I show how playing reversible pebble ga
mes relate to implementing operations on a quantum computer while trading
off space (number of available qubits = number of pebbles P) to time (numb
er of operations within the coherence time ~ number of moves). I show heur
istics and optimum strategies to solve the pebble game based on SAT solver
s. Variants of the pebble game are presented that are especially suitable
for fault-tolerant quantum computers in the context of quantum crypto anal
ysis. These pebble games are based on logic networks over AND\, XOR\, and
NOT gates\, with logic synthesis algorithms aiming at reducing the multipl
icative complexity of these networks. The talk is based on the papers arXi
v:1904.02121 and arXiv:1908.01609
LOCATION:BC 410 https://plan.epfl.ch/?room==BC%20410
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR