Optimal synthesis of multiple output Boolean functions using a set of quantum gates by symbolic reachability analysis

TLDR

Previous quantum logic synthesis relied on permutative reversible gates, whereas this work uses a lower‑level library that includes nonpermutative quantum gates. The study proposes an optimal quantum‑circuit synthesis method based on symbolic reachability analysis, handling binary inputs/outputs and nonbinary internal signals. The method employs symbolic reachability analysis to minimize quantum cost, offers speed‑up variants, applies to small reversible functions, and can convert irreversible functions into reversible circuits, enabling synthesis of arbitrary multi‑output Boolean functions with the chosen quantum gate library. The approach yields minimum‑cost quantum circuits for Miller, half‑adder, full‑adder, Fredkin, Peres, and Toffoli gates, outperforming prior results, and represents the first successful use of formal methods and SAT in quantum logic synthesis.

Abstract

This paper proposes an approach to optimally synthesize quantum circuits by symbolic reachability analysis, where the primary inputs and outputs are basis binary and the internal signals can be nonbinary in a multiple-valued domain. The authors present an optimal synthesis method to minimize quantum cost and some speedup methods with nonoptimal quantum cost. The methods here are applicable to small reversible functions. Unlike previous works that use permutative reversible gates, a lower level library that includes nonpermutative quantum gates is used here. The proposed approach obtains the minimum cost quantum circuits for Miller gate, half adder, and full adder, which are better than previous results. This cost is minimum for any circuit using the set of quantum gates in this paper, where the control qubit of 2-qubit gates is always basis binary. In addition, the minimum quantum cost in the same manner for Fredkin, Peres, and Toffoli gates is proven. The method can also find the best conversion from an irreversible function to a reversible circuit as a byproduct of the generality of its formulation, thus synthesizing in principle arbitrary multi-output Boolean functions with quantum gate library. This paper constitutes the first successful experience of applying formal methods and satisfiability to quantum logic synthesis.