  Reversible logic has attracted much research interest over the last few
decades, especially due to its application in quantum computing. In the
construction of reversible gates from basic gates, ancilla bits are commonly
used to remove restrictions on the type of gates that a certain set of basic
gates generates. With unlimited ancilla bits, many gates (such as Toffoli and
Fredkin) become universal reversible gates. However, ancilla bits can be
expensive to implement, thus making the problem of minimizing necessary ancilla
bits a practical topic.
  This thesis explores the problem of reversible logic synthesis using a single
base gate and a few ancilla bits. Two base gates are discussed: a variation of
the 3-bit Toffoli gate and the original 3-bit Fredkin gate. There are three
main results associated with these two gates: i) the variated Toffoli gate can
generate all n-bit reversible gates using 1 ancilla bit, ii) the variated
Toffoli can generate all n-bit reversible gates that are even permutations
using no ancilla bit, iii) the Fredkin gate can generate all n-bit conservative
reversible gates using 1 ancilla bit. Prior to this paper, the best known
result for general universality requires three basic gates, and the best known
result for conservative universality needs 5 ancilla bits. The second result is
trivially optimal. For the first and the third result, we explicitly prove
their optimality: the variated Toffoli cannot generate all n-bit reversible
gates without using any extra input lines, and the Fredkin gate cannot generate
all n-bit conservative reversible gates without using extra input lines. We
also explore a stronger version of the second converse by introducing a new
concept called borrowed bits, and prove that the Fredkin gate cannot generate
all n-bit conservative reversible gates without ancilla bits, even with an
unlimited number of borrowed bits.
