Yang et al. investigate the construction of reversible logic gates without constants. The key area of application is quantum computing. The basic idea of reversible computing is to avoid destroying bits. This has the physical correlate that energy dissipation can, in ideal circumstances, be reduced to zero. The method involves the design of a majority-based reversible logic gate (MBRLG) with 2k+1 inputs and 2k+1 outputs. At least one of these output lines has the value 1 if and only if more than half of the inputs are 1.

By carefully analyzing the combinatorics of input and output configurations under the MBRLG constraint, and identifying the requisite symmetries so induced, the authors show by explicit calculation how to construct these gates (at least in principle) for any k using the computer algebra package GAP. The paper carries this out for small values of k, in keeping with the authors’ interest in the most efficient realization of certain quantum operations. Of interest is the authors’ use of permutations as generators of the appropriate symmetry group for each MBRLG studied. These generators are arrived at by combinatorial reasoning, and are then used as inputs for subsequent calculation of the generated group by GAP. The group order coincides with the maximum possible number of input-output arrangements, which is used to show that the proposed gate satisfies the MBRLG constraint.