# Reformulation of BQP to SDP

I run into the following reading some optimization papars:

$$\min_x x^TAx$$ where $x\in\{-1,1\}^n$ and $A\in S_n$, Is equivalent to $$\min <X,A>$$ s.t $diag(X) = (1,1,...,1)\;\; rank(X) = 1$. I guess $<.,.>$ is the Frobenius scalar product. How can we see that those are the same? Through the Lagrangian? Sorry for bad Latex I could not find anywhere how to write in optimization problems.

-
I don't get it, $x\in \{-1,1\}$? If that's the case, in order to $x^TAx$ be defined it's necessary that $A$ is a $1\times 1$ matrix. Is that the case? And if it is, then $x^TAx=A$, for any $x\in \{-1,1\}$. – Git Gud Jan 12 '13 at 13:26
sorry for the typos, you understand now? – Johan Jan 12 '13 at 13:34
The commands for angle brackets are \langle and \rangle. For operator names that are not built into LaTeX, use \operatorname{diag}. – user53153 Jan 12 '13 at 23:42

Notice that in general $(A \in S_n)$
$$\min_x x^TAx = \min_x tr(x^TAx) = \min_x tr(Axx^T)=\min_X \langle A,X \rangle,$$ where $X=xx^T$ so obviously $rank(X)=1$. Now the following sets in $\mathbb{R}^n$ $\{x:x_i\in\{-1,1\}\},\{x:x^2_i=1\},\{x:\operatorname{diag}(xx^T)=1\}$ are equivalent so therefore the constraint $x\in\{-1,1\}^n$ is equivalent to $\operatorname{diag}(X) = (1,1,...,1)$. It follows that the problems are equivalent.