Abstracts

Reversible circuit compilation with space constraints

Presenting Author: Martin Roetteler, (Microsoft)
Contributing Author(s): Alex Parent (IQC Waterloo), Krysta M. Svore (Microsoft Research)

We develop a framework for resource efficient compilation of higher-level programs into lower-level reversible circuits. Our main focus is on optimizing the memory footprint of the resulting reversible networks. This is motivated by the limited availability of qubits for the foreseeable future. We apply three main techniques to keep the number of required qubits small when computing classical, irreversible computations by means of reversible networks: first, wherever possible we allow the compiler to make use of in-place functions to modify some of the variables. Second, an intermediate representation is introduced that allows to trace data dependencies within the program, allowing to clean up qubits early. This realizes an analog to “garbage collection” for reversible circuits. Third, we use the concept of so-called pebble games to transform irreversible programs into reversible programs under space constraints, allowing for data to be erased and recomputed if needed. We introduce REVS, a compiler for reversible circuits that can translate a subset of the functional programming language F# into Toffoli networks. We discuss a number of test cases that illustrate the advantages of our approach including reversible implementations of SHA-2 and other cryptographic hash-functions, reversible integer arithmetic, as well as a test-bench of combinational circuits used in classical circuit synthesis. Compared to Bennett's method, REVS can reduce space complexity by a factor of 4 or more, while having an only moderate increase in circuit size as well as in the time it takes to compile the reversible networks.

(Session 9c : Friday from 5:00 pm - 5:30 pm)

 

SQuInT Chief Organizer
Prof. Akimasa Miyake
amiyake@unm.edu

SQuInT Co-Organizer
Prof. Elohim Becerra
fbecerra@unm.edu

SQuInT Founder
Prof. Ivan Deutsch
ideutsch@unm.edu

SQuInT Administrator
Gloria Cordova
gjcordo1@unm.edu
505 277-1850

Tweet About SQuInT 2016!