Given a (sparse, or banded if it make things easier) matrix $Q \in \{-1, 0,1\}^{n \times m}$, where $m \gg n$, I want to solve the following optimization problem
$$\max_{v, w \in \{\pm 1\}^n} v Q w^{T}$$
I guess it's in NP. Is there a name or efficient algorithm for this kind of problem? Is it possible to reformulate it as like Max-Cut problem?
On
While it's not necessarily the most elegant way of stating it, your problem can be stated as a (quadratically constrained) quadratic program. It can be put in the standard form., Let $$ \vec{u}=\begin{bmatrix}\vec{v} \\ \vec{w}\end{bmatrix},\ \ \ A=\frac 12\begin{bmatrix}0 & Q^T \\ Q & 0\end{bmatrix} $$ Then the problem is to minimize $\vec{u}^TA\vec{u}$ subject to $u_i^2=1\ \forall i$.
If convenient, it's also possible to change variables/constraints such that the problem is a $\{0,1\}$ quadratic integer programming problem, which may be a bit more standard. $$ \vec{x}=\frac{\vec{u}+\vec{1}}{2},\ \ \ \vec{a}=\frac{1}{2}A\vec{1} $$ $$ \text{minimize}\ \ \ \vec{x}^TA\vec{x}-\vec{a}^T\vec{x} $$ $$ \text{subject to}\ \ \ \vec{x}\in\{0,1\}^{m+n} $$ It's not totally clear with the constraints, but the complexity almost certainly depends on the definiteness of $A$. If A is indefinite, it is almost certainly NP-hard (w.r.t. letting $m,n\to\infty$ with fixed $m/n$), since it is nonconvex. If A is positive (semi)definite then polynomial time is probably attainable.
On
With changes of variables $(v+1)/2$ and $(w+1)/2$, this is quadratic unconstrained binary optimization: https://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization
Quadratic Integer Programming.
See en.wikipedia.org/wiki/Quadratic_programming for solution approaches.