  The design and optimization of quantum circuits is central to quantum
computation. This paper presents new algorithms for compiling arbitrary 2^n x
2^n unitary matrices into efficient circuits of (n-1)-controlled single-qubit
and (n-1)-controlled-NOT gates. We first present a general algebraic
optimization technique, which we call the Palindrome Transform, that can be
used to minimize the number of self-inverting gates in quantum circuits
consisting of concatenations of palindromic subcircuits. For a fixed column
ordering of two-level decomposition, we then give an numerative algorithm for
minimal (n-1)-controlled-NOT circuit construction, which we call the
Palindromic Optimization Algorithm. Our work dramatically reduces the number of
gates generated by the conventional two-level decomposition method for
constructing quantum circuits of (n-1)-controlled single-qubit and
(n-1)-controlled-NOT gates.
