<p>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.</p>

<p>Here was an early example: solving a <a href="http://www.scottaaronson.com/papers/bfpsiam.pdf" rel="noreferrer">problem of mine</a> from 2000, in 2003 <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.113.1101&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Barnum, Saks, and Szegedy</a> showed that Q(f), the quantum query complexity of a Boolean function f:{0,1}<sup>n</sup>&rarr;{0,1}, can be computed in time polynomial in 2<sup>n</sup> (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 2<sup>n</sup>-sized) unitary matrices.  Barnum et al. reduced to SDP by exploiting a "duality" between unitary matrices and positive semidefinite matrices, the so-called <a href="http://en.wikipedia.org/wiki/Channel-state_duality" rel="noreferrer">Choi-Jamiolkowski isomorphism</a>.  For a more recent and simpler SDP characterizing Q(f), see <a href="http://eccc.hpi-web.de/report/2010/110/" rel="noreferrer">Reichardt's 2010 paper</a> showing that the negative-weight adversary method is optimal.</p>

<p>Another important case where this trick has been exploited is in quantum interactive proof systems.  While it's not intuitively obvious, in 2000 <a href="https://cs.uwaterloo.ca/~watrous/Papers/Quantum%20Interactive%20Proofs.pdf" rel="noreferrer">Kitaev and Watrous</a> 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 <a href="http://arxiv.org/abs/0907.4737" rel="noreferrer">QIP=PSPACE breakthrough</a> came from showing that that particular SDP could be approximately solved even better, in NC (i.e., by log-depth circuits).</p>

<p>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!</p>

CC BY-SA 3.0
2016-03-08T11:54:13.307Z
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.
Joris
CC BY-SA 3.0
2012-10-20T14:30:10.190Z
2012-10-20T22:05:06.613Z
2012-10-20T22:05:06.613Z
Scott Aaronson
<p>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.</p>

CC BY-SA 3.0
2012-10-16T20:03:34.863Z
this is not what the paper says. the paper is about "hadamard equivalence" of $\pm 1$ matrices
Sasho Nikolov
CC BY-SA 3.0
2012-10-16T19:13:04.547Z
2012-10-16T19:13:04.547Z
Dursun
<p>What is the computational complexity of optimizing various functions over the unitary group $\mathcal{U}(n)$? </p>

<p>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)</p>

CC BY-SA 3.0
2012-05-14T01:09:00.017Z
are you okay to restrict "various functions" to "polynomials over the unitaries"?
Artem Kaznatcheev
CC BY-SA 3.0
2012-05-14T02:17:33.050Z
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?
Robin Kothari
CC BY-SA 3.0
2012-05-14T02:25:40.730Z
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: http://www.eecs.berkeley.edu/~sburden/research/jonathan/Brockett1991.pdf
Suresh Venkat
CC BY-SA 3.0
2012-05-14T03:56:37.770Z
@Artem: yes, in practice polynomials of low degrees are the most relevant, I think.
Marcin Kotowski
CC BY-SA 3.0
2012-05-15T22:38:11.437Z
@SureshVenkat that's interesting. so some form of these problems is equivalent to linear programming, modulo the blow up introduced by the reduction. maybe there is an answer to the question in what you wrote :)
Sasho Nikolov
CC BY-SA 3.0
2012-05-16T02:18:20.637Z
Well not really because there is no complexity result in his paper.
Suresh Venkat
CC BY-SA 3.0
2012-10-17T03:08:02.063Z
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?
Niel de Beaudrap
<cc.complexity-theory><reference-request><optimization><quantum-information>
Complexity of optimization over unitary group
Marcin Kotowski
# Complexity of optimization over unitary group

(Asked by: username_0 on 2012-05-14)

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)

**Tags:** cc.complexity-theory, reference-request, optimization, quantum-information

> **Comments:**
> **username_1**: are you okay to restrict "various functions" to "polynomials over the unitaries"?  
> **username_2**: 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?  
> **username_3**: 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: http://www.eecs.berkeley.edu/~sburden/research/jonathan/Brockett1991.pdf  
> **username_0**: @Artem: yes, in practice polynomials of low degrees are the most relevant, I think.  
> **username_4**: @SureshVenkat that's interesting. so some form of these problems is equivalent to linear programming, modulo the blow up introduced by the reduction. maybe there is an answer to the question in what you wrote :)  
> **username_3**: Well not really because there is no complexity result in his paper.  
> **username_5**: 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?  

---

## 2 answers

### Answer by username_6 on 2012-10-20. Score: 16

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](http://www.scottaaronson.com/papers/bfpsiam.pdf) from 2000, in 2003 [Barnum, Saks, and Szegedy](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.113.1101&rep=rep1&type=pdf) 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](http://en.wikipedia.org/wiki/Channel-state_duality). For a more recent and simpler SDP characterizing Q(f), see [Reichardt's 2010 paper](http://eccc.hpi-web.de/report/2010/110/) 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](https://cs.uwaterloo.ca/~watrous/Papers/Quantum%20Interactive%20Proofs.pdf) 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](http://arxiv.org/abs/0907.4737) 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!

> **Comments:**
> **username_7**: 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.  

---

### Answer by username_8 on 2012-10-16. Score: -3

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.

> **Comments:**
> **username_4**: this is not what the paper says. the paper is about "hadamard equivalence" of $\pm 1$ matrices  

---

