  Determining the quantum circuit complexity of a unitary operation is closely
related to the problem of finding minimal length paths in a particular curved
geometry [Nielsen et al, Science 311, 1133-1135 (2006)]. This paper
investigates many of the basic geometric objects associated to this space,
including the Levi-Civita connection, the geodesic equation, the curvature, and
the Jacobi equation. We show that the optimal Hamiltonian evolution for
synthesis of a desired unitary necessarily obeys a simple universal geodesic
equation. As a consequence, once the initial value of the Hamiltonian is set,
subsequent changes to the Hamiltonian are completely determined by the geodesic
equation. We develop many analytic solutions to the geodesic equation, and a
set of invariants that completely determine the geodesics. We investigate the
problem of finding minimal geodesics through a desired unitary, U, and develop
a procedure which allows us to deform the (known) geodesics of a simple and
well understood metric to the geodesics of the metric of interest in quantum
computation. This deformation procedure is illustrated using some three-qubit
numerical examples. We study the computational complexity of evaluating
distances on Riemmanian manifolds, and show that no efficient classical
algorithm for this problem exists, subject to the assumption that good
pseudorandom generators exist. Finally, we develop a canonical extension
procedure for unitary operations which allows ancilla qubits to be incorporated
into the geometric approach to quantum computing.
