What is the computational complexity of optimizing various functions over the unitary group $\mathcal{U}(n)$? A typical task, arising often in quantum information theory, would be maximizing a quantity of type $\mathrm{Tr}AUBU^{\dagger}$ (or higher order polynomials in $U$) over all unitary matrices $U$. Is this type of optimization efficiently (perhaps approximately) computable, or is it NP-hard? (maybe this is well known, but I've been unable to find any general references)
Complexity of optimization over unitary group
cc.complexity theory;reference request;optimization;quantum information