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)

  • 3
    $\begingroup$ are you okay to restrict "various functions" to "polynomials over the unitaries"? $\endgroup$ May 14, 2012 at 1:09
  • 2
    $\begingroup$ I don't know much about how these problems arise, but what would be the natural classical analogue of this problem? Do you know the complexity of that problem? $\endgroup$ May 14, 2012 at 2:17
  • 7
    $\begingroup$ There's a very nice paper by Roger Brockett from 1991 that shows how to express sorting and linear programming in essentially the form you describe, but over the orthogonal matrices. No mention of complexity though,but the fact that two very different problems can be expressed the same way means that you'll need to know something about the problem structure to make a complexity determination: eecs.berkeley.edu/~sburden/research/jonathan/Brockett1991.pdf $\endgroup$ May 14, 2012 at 2:25
  • $\begingroup$ @Artem: yes, in practice polynomials of low degrees are the most relevant, I think. $\endgroup$ May 14, 2012 at 3:56
  • 3
    $\begingroup$ It comes down to eigen-decompositions of $A$ and $B$ in the degree-2 example you give. For $A$ and $B$ hermitian, the unitary $U$ can be used to maximize the trace by having the eigenspaces of $U B U^\dagger$ align with those of $A$; it then suffices to maximise the dot-product of the sequences of their eigenvalues, which is trivial if $A$ and $B$ are positive semidefinite (and a case to which we may reduce by adding multiples of the identity to rescale eigenvalues). Or are you interested in much more general cases, not necessarily motivated by quantum mechanics on small-dimensional systems? $\endgroup$ Oct 17, 2012 at 3:08

2 Answers 2


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→{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 ⊆ 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!

  • $\begingroup$ Dear Scott! Barnum, Saks, and Szegedy don't explicitly mention the Choi-Jamiolkowski isomorphism, and I don't understand how this is related to their construction. Could you please elaborate on this? I am asking because I am trying to understand if a similar result is possible for the case of faulty oracles. $\endgroup$
    – Joris
    Mar 8, 2016 at 11:54

Determining whether two Hadamard matrices are equivalent is a Graph Isomorphism (GI) complete problem. Brendon McKay has a paper on this topic. See B. D. McKay, Hadamard equivalence via graph isomorphism, Discrete Mathematics, 27 (1979) 213-216.

  • 1
    $\begingroup$ this is not what the paper says. the paper is about "hadamard equivalence" of $\pm 1$ matrices $\endgroup$ Oct 16, 2012 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.