Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 339 / 2 / a

Split the sign vector as $x=(p^T,q^T{)}^T$. Multiplication of the two off-diagonal blocks givesbecause the two terms are the same real scalar. The map $(p,q)\mapsto x$ is a bijection between the feasible sign choices. ThereforeThis is the symmetric lifting of bipartite binary quadratic optimization to binary quadratic optimization. The factor $1/2$ is necessary: otherwise the two blocks would double the objective. No positive semidefiniteness of $A$ is assumed; generally its off-diagonal structure makes its quadratic form indefinite.