  A quantum computer directly manipulates information stored in the state of
quantum mechanical systems. The available operations have many attractive
features but also underly severe restrictions, which complicate the design of
quantum algorithms. We present a divide-and-conquer approach to the design of
various quantum algorithms. The class of algorithm includes many transforms
which are well-known in classical signal processing applications. We show how
fast quantum algorithms can be derived for the discrete Fourier transform, the
Walsh-Hadamard transform, the Slant transform, and the Hartley transform. All
these algorithms use at most O(log^2 N) operations to transform a state vector
of a quantum computer of length N.
