  This paper proves the polynomial equivalence of a broad class of definitions
of quantum computational complexity. We study right-invariant metrics on the
unitary group -- often called `complexity geometries' following the definition
of quantum complexity proposed by Nielsen -- and delineate the equivalence
class of metrics that have the same computational power as quantum circuits.
Within this universality class, any unitary that can be reached in one metric
can be approximated in any other metric in the class with a slowdown that is
at-worst polynomial in the length and number of qubits and inverse-polynomial
in the permitted error. We describe the equivalence classes for two different
kinds of error we might tolerate: Killing-distance error, and operator-norm
error. All metrics in both equivalence classes are shown to have exponential
diameter; all metrics in the operator-norm equivalence class are also shown to
give an alternative definition of the quantum complexity class BQP.
  My results extend those of Nielsen et al., who in 2006 proved that one
particular metric is polynomially equivalent to quantum circuits. The Nielsen
et al. metric is incredibly highly curved. I show that the greatly enlarged
equivalence class established in this paper also includes metrics that have
modest curvature. I argue that the modest curvature makes these metrics more
amenable to the tools of differential geometry, and therefore makes them more
promising starting points for Nielsen's program of using differential geometry
to prove complexity lowerbounds.
