We show how to construct quantum gate arrays that can be programmed to perform different unitary operations on a data register, depending on the input to some program register. It is shown that a universal quantum gate array - a gate array which can be programmed to perform any unitary operation - exists only if one allows the gate array to operate in a probabilistic fashion. The universal quantum gate array we construct requires an exponentially smaller number of gates than a classical universal gate array.

3 pages, REVTEX. Submitted to Phys. Rev. Lett