Complexity of optimization over unitary group
Sorry I'm late!  In quantum computing theory, there are lots of examples of optimization problems over the unitary group that, surprisingly (at least to me), are solvable in (classical) polynomial time by reduction to semidefinite programming.

Here was an early example: solving a problem of mine from 2000, in 2003 Barnum, Saks, and Szegedy showed that Q(f), the quantum query complexity of a Boolean function f:{0,1}n&rarr;{0,1}, can be computed in time polynomial in 2n (i.e., the size of f's truth table).  I had thought about this but couldn't see how to do it, since one needs to optimize the success probability over all possible quantum query algorithms, each one with its own set of (possibly 2n-sized) unitary matrices.  Barnum et al. reduced to SDP by exploiting a "duality" between unitary matrices and positive semidefinite matrices, the so-called Choi-Jamiolkowski isomorphism.  For a more recent and simpler SDP characterizing Q(f), see Reichardt's 2010 paper showing that the negative-weight adversary method is optimal.

Another important case where this trick has been exploited is in quantum interactive proof systems.  While it's not intuitively obvious, in 2000 Kitaev and Watrous proved that QIP &sube; EXP. by reducing the problem of optimizing over the exponential-sized unitary matrices that arise in a 3-round quantum interactive proof system, to solving a singly-exponential-sized SDP (again, I think, using the Choi-Jamiolkowski isomorphism between mixed states and unitary matrices).  The recent QIP=PSPACE breakthrough came from showing that that particular SDP could be approximately solved even better, in NC (i.e., by log-depth circuits).

So, whatever your specific optimization problem involving the unitary group, my guess is that it can be solved faster than you think -- if not in some even simpler way, then by reduction to SDP!