  A universal quantum processor is a device that takes as input a (quantum)
program, containing an encoding of an arbitrary unitary gate, and a (quantum)
data register, on which the encoded gate is applied. While no perfect universal
quantum processor can exist, approximate processors have been proposed in the
past two decades. A fundamental open question is how the size of the smallest
quantum program scales with the approximation error. Here we answer the
question, by proving a bound on the size of the program and designing a
concrete protocol that attains the bound in the asymptotic limit. Our result is
based on a connection between optimal programming and the Heisenberg limit of
quantum metrology, and establishes an asymptotic equivalence between the tasks
of programming, learning, and estimating unitary gates.
