Reformulation of BQP to SDP

Question

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.

Answer 1

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.