Reversible Circuit Compilation with Space Constraints

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 which can then be further interpreted for instance in LIQuiji, a domain-specific
language for quantum computing and which is also embedded into F#. 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.