Playing Reversible Pebble Games for Quantum Memory Management

Dr. Mathias Soeken EPFL Tuesday, November 19, 2019 @ 4:15 pm Room BC 410 Hosted by: Prof. Giovanni De Micheli

Abstract

The reversible pebble game is played on a connected directed acyclic graph with marked vertices. Starting 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 of 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 move by marking or unmarking a vertex, if and only if all its ingoing adjacent 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 the 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 games relate to implementing operations on a quantum computer while trading off space (number of available qubits = number of pebbles P) to time (number of operations within the coherence time ~ number of moves). I show heuristics and optimum strategies to solve the pebble game based on SAT solvers. Variants of the pebble game are presented that are especially suitable for fault-tolerant quantum computers in the context of quantum crypto analysis. These pebble games are based on logic networks over AND, XOR, and NOT gates, with logic synthesis algorithms aiming at reducing the multiplicative complexity of these networks.

The talk is based on the papers arXiv:1904.02121 and arXiv:1908.01609

Bio

Mathias Soeken works as a research design engineer at Microsoft 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 regularly 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 University of Bremen, Germany (2013). His research interests are logic synthesis, quantum computing, reversible logic, and formal verification. Mathias Soeken is member of the IEEE and of the ACM.