BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Playing Reversible Pebble Games for Quantum Memory Management
DTSTART:20191119T161500
DTEND:20191119T170000
DTSTAMP:20260407T111152Z
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