  Quantum compiling addresses the problem of approximating an arbitrary quantum
gate with a string of gates drawn from a particular finite set. It has been
shown that this is possible for almost all choices of base sets and furthermore
that the number of gates required for precision epsilon is only polynomial in
log 1/epsilon. Here we prove that using certain sets of base gates quantum
compiling requires a string length that is linear in log 1/epsilon, a result
which matches the lower bound from counting volume up to constant factor.
