Martin Roetteler: Reversible Circuit Compilation with Space Constraints

Martin Roetteler (Microsoft)
Reversible Circuit Compilation with Space Constraints
QuICS Workshop on the Frontiers of Quantum Information and Computer Science (October 2, 2015)

I will present REVS, a tool for resource-aware compilation of higher-level, irreversible programs into lower-level, reversible circuits over a universal gate set such as the Toffoli gates. 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. REVS can translate programs that are expressed in a subset of the functional programming language F# into Toffoli networks which can then be further processed.

We employ three main ideas to optimize the number of required ancilla qubits: (1) whenever possible, we allow the compiler to make use of in-place functions to compute expressions; (2) we introduce an intermediate representation that allows tracking data dependencies within the program. This allows identifying subsets of qubits that are no longer needed for subsequent parts of the computation, allowing those qubits to be cleaned up early; (3) we use a heuristic which corresponds to pebble games played on the dependency graph to transform irreversible programs into reversible circuits under an overall space constraint.

We discuss a number of examples to illustrate our compilation strategy for problems at scale, including a reversible implementation of hash functions such as SHA-256, automatic generation of reversible integer arithmetic from irreversible descriptions, as well as a test-bench of Boolean circuits that is used by the classical Circuits and Systems community.

Our main findings are that, when compared with Bennett's original “compute-copy-uncompute,” it is possible to reduce the space complexity by 75 percent or more, at the price of having an only moderate increase in circuit size as well as in compilation time.