From Classical Universal and Reversible Logical Operations to Quantum Computation

Reversible logical operations implemented via reversible logic gates (that can be realized in practice, at least approximately, using various physical processes) play an important role in both low-power electronics [1, 2] and quantum compu-tations [3]. First, reversibility of classical computational circuits helps to avoid additional energy dissipation and heat generation that is immanently tied to irre-versible computation due to Landauer’s principle [4]. Second, quantum gates and quantum circuits have to be reversible due to the very nature of unitary quantum evolution [5]. Here different classification schemes of reversible logical operations, including but not restricted to those obtained via group–theoretical methods, are presented for different logic widths of corresponding gates. Searching for universal subsets of reversible gates is undertaken with the help of computer algebra systems. New re-sults and nontrivial observations are provided as compared to the pioneering paper [6]. Novel less-typical reversible and universal logic gates are discussed and their possible applications are suggested. Some remarks concerning optimal designs o