  What is the minimal size quantum circuit required to exactly implement a
specified n-qubit unitary operation, U, without the use of ancilla qubits? We
show that a lower bound on the minimal size is provided by the length of the
minimal geodesic between U and the identity, I, where length is defined by a
suitable Finsler metric on SU(2^n). The geodesic curves of such a metric have
the striking property that once an initial position and velocity are set, the
remainder of the geodesic is completely determined by a second order
differential equation known as the geodesic equation. This is in contrast with
the usual case in circuit design, either classical or quantum, where being
given part of an optimal circuit does not obviously assist in the design of the
rest of the circuit. Geodesic analysis thus offers a potentially powerful
approach to the problem of proving quantum circuit lower bounds. In this paper
we construct several Finsler metrics whose minimal length geodesics provide
lower bounds on quantum circuit size, and give a procedure to compute the
corresponding geodesic equation. We also construct a large class of solutions
to the geodesic equation, which we call Pauli geodesics, since they arise from
isometries generated by the Pauli group. For any unitary U diagonal in the
computational basis, we show that: (a) provided the minimal length geodesic is
unique, it must be a Pauli geodesic; (b) finding the length of the minimal
Pauli geodesic passing from I to U is equivalent to solving an exponential size
instance of the closest vector in a lattice problem (CVP); and (c) all but a
doubly exponentially small fraction of such unitaries have minimal Pauli
geodesics of exponential length.
