  Reversible or information-lossless circuits have applications in digital
signal processing, communication, computer graphics and cryptography. They are
also a fundamental requirement in the emerging field of quantum computation. We
investigate the synthesis of reversible circuits that employ a minimum number
of gates and contain no redundant input-output line-pairs (temporary storage
channels). We prove constructively that every even permutation can be
implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We
describe an algorithm for the synthesis of optimal circuits and study the
reversible functions on three wires, reporting distributions of circuit sizes.
We study circuit decompositions of reversible circuits where gates of the same
type are next to each other. Finally, in an application important to quantum
computing, we synthesize oracle circuits for Grover's search algorithm, and
show a significant improvement over a previously proposed synthesis algorithm.
