  We prove upper and lower bounds relating the quantum gate complexity of a
unitary operation, U, to the optimal control cost associated to the synthesis
of U. These bounds apply for any optimal control problem, and can be used to
show that the quantum gate complexity is essentially equivalent to the optimal
control cost for a wide range of problems, including time-optimal control and
finding minimal distances on certain Riemannian, subriemannian, and Finslerian
manifolds. These results generalize the results of Nielsen, Dowling, Gu, and
Doherty, Science 311, 1133-1135 (2006), which showed that the gate complexity
can be related to distances on a Riemannian manifold
