Computing classical functions is at the core of many quantum algorithms. Conceptually any classical, irreversible function can be carried out by a Toffoli network in a reversible way. However, the Bennett method to obtain such a network in a "clean" form, i.e., a form that can be used in quantum algorithms, is highly space-inefficient. We present REVS, a tool that allows to trade time against space, leading to circuits that have a significantly smaller memory footprint when compared to the Bennett method. Our method is based on an analysis of the data dependency graph underlying a given classical program. We report the findings from running the tool against several benchmarks circuits to highlight the potential space-time tradeoffs that REVS can realize.
展开▼
