ED1-5

Optimization of Reversible Logic Synthesis for Adiabatic Quantum-Flux-Parametron Logic
*Ro Saito1, Christopher L. Ayala2, Naoki Takeuchi2, Taiki Yamae1, Nobuyuki Yoshikawa1

1. Reversible Logic Synthesis
The adiabatic quantum-flux-parametron (AQFP) is the basic building block for extremely energy efficient superconductor logic. Thus far, we mainly use AQFP circuits for classical computation, however, we have already shown that a physically and logically reversible gate can be designed using a few AQFP gates. We call such a reversible gate the Reversible-QFP (RQFP) gate.  In irreversible circuits, there exists at least a minimum amount of energy dissipated from information loss. For example, a 2-input 1-output logic gate exhibits information loss, so it must be accompanied by an increase of entropy no matter how well-designed the logic device is. However, in reversible computing there is no increase in entropy from computation. Its energy dissipation comes from just the physical non-idealities and parasitics of the reversible circuit. A reversible gate maps an input vector to an output vector one-by-one, and a reversible circuit is composed of only reversible gates. Whereas an AQFP circuit can be driven with exceptionally low energy as low as 1.4zJ per Josephson junction at 4.2K, an RQFP circuit can be even more energy efficient in exchange for an increase in the number of circuit elements.

Some reversible logic synthesis tools have already been developed for quantum computing circuits. However, many of them assume the use of the Toffoli gate as the reversible gate, and the algorithms to synthesize the reversible circuits assume the logical properties of the Toffoli gate. Due to differences in the truth table between the Toffoli gate and the RQFP gate, we cannot utilize existing reversible logic synthesis tools for RQFP circuits. Thus, we propose a new methodology for synthesizing RQFP circuits, and we implemented a tool called “RQFP synthesizer” for generating RQFP circuits automatically. The logic function of the circuits generated from the tool were successfully verified, and it was shown that the methodology can successfully synthesize an RQFP circuit.

RQFP synthesizer refers to Hierarchical Reversible Logic Synthesis (proposed by Mathias et al. [1]) for generating an RQFP circuit, the input circuit is converted into a k-LUT network format. k-LUT network is a directed-acyclic-graph which expresses a circuit and all nodes as a k-input 1-output LUT. If each node can be converted into a circuit which consists of only RQFP gates, the whole circuit becomes a reversible circuit. For instance, there are 256 possible logic patterns that can be assigned to a 3-LUT, thus 256 patterns must be made by combining some RQFP gates and using some additional constant inputs (ancilla line) for the 3-LUT network. We already showed that all patterns of a 3-LUT and 2-LUT can be composed of at most 5 levels of RQFP gates and at most 2 ancilla lines. They are calculated and stored into a database in advance, therefore the tool can convert an input circuit only by referring to pre-calculated patterns from a database. We showed that the RQFP synthesizer can generate reversible circuits and that synthesized circuits have almost ten times larger JJ counts than conventional circuits [2].

2. Optimization
The number of inputs and JJs becomes quite large if optimization algorithms are not applied. The cause of large I/O numbers is garbage lines that remain uncomputed. By reusing garbage lines, we can potentially save in I/O pins and JJs. It is difficult to reuse uncomputed outputs, therefore reclaiming ancilla lines is one of the ways to make them more manageable.

The Benett trick is an already known technique to reclaim ancilla lines from outputs. The Benett trick requires some additional ancilla lines to store the calculation result, however, after the evacuation, output lines can be uncomputed, therefore input ancilla lines can be reclaimed. Reclaimed ancilla lines are commonly usable like normal ancilla lines.

Allocation of ancilla line between candidate ancilla lines and nodes requiring ancilla lines is a combinatorial problem, thus it is difficult to finish computing in a reasonable time by exhaustive search. Hence heuristic algorithms such as the genetic algorithm are suitable for finding a suboptimal solution. We will show the effectiveness of optimization in this presentation.

[1] M. Soeken, et al. arXiv preprint arXiv:1706.02721, 2017.
[2] R. Saito, et al. Reversible Logic Synthesis for Adiabatic Quantum-Flux-Parametron Logic. Poster Presented at: EUCAS 2021; September 5-9, 2021; MOSCOW.

Keywords: AQFP, Logic Synthesis, Reversible Circuit, Optimization