I am unexperienced in integer optimizations, but needed to solve $$\max_{\boldsymbol{x} \in \{\pm 1\}^N}\; \boldsymbol{x}^{\mathrm{T}}G\boldsymbol{x}$$ where $G$ is a real-valued $N\times N$ positive semidefinite matrix of (low) rank $r$.
Since I found it fun, I didn't read up much before proceeding to work. For $r>1$ I managed to show that the problem can be solved exactly with complexity $\mathcal{O}\left(N^{r-1}\right)$.
Next I started to read literature, but typically only came across the case of a minimization with a high-rank positive semi-definite matrix $G$. I assume that the reason is that my case is too simple to be studied. I now wonder if there are any good references for my case.
Thanks/Fredrik
The reason you only found minimization has to do with convexity. Exact algorithms for integer programs (algorithms guaranteed to find a provable optimum, given enough time and memory) frequently follow some version of the branch-and-bound framework, which requires the ability to compute bounds (lower bounds for minimization problems, upper bounds for maximization problems) efficiently given partial solutions. This is commonly done by solving the continuous relaxation of the problem, which in your case would mean replacing the domain $\lbrace \pm 1 \rbrace ^N$ with the hypercube $[-1, 1]^N$. The minimum (maximum) of a convex (concave) function is relatively easy to find. Your objective function is convex, but you need the maximum, which is where things get sticky.
By doing a variable conversion from $x_i\in \lbrace -1, 1\rbrace$ to $y_i\in \lbrace 0, 1\rbrace$, your problem becomes a quadratic unconstrained binary optimization (QUBO) problem. You might want to dig into the literature on QUBOs.