Indefinite Boolean Quadratic Programming: number of minima The Boolean Quadratic Programming problem is defined as follows
$$\displaystyle\min_{x \in \{0,1\}^n} f(x) = x^TQx + c^Tx$$
It is a well-studied NP-hard problem with many approximation algorithms proposed. I am interested in finding the number of minima given arbitrary $Q, c$.
If the problem as such is not well-studied then we can simplify it by adding some special conditions on $Q$ (like positive definiteness). In the worst case can we determine the number of minima if we remove the Boolean restriction and consider $x \in \mathbb R^n$ or $ x \in [0,1]^n$?
If there are papers or online links that I can refer that will help me sort this problem out, it will be of great help.
Thanks!
 A: 1, The proposed theory
If an irrational sequential analysis was applied under huge dimension, it will need much time because the Boolean vector has $2^n$ combinations. Hence, the other rational algorithms are necessary. For definition, we suppose a real symmetric matrix $Q=[q_{ij}]\in\mathbf{R}^{n\times n}$ so that $Q=Q^{\text{T}}$ and $q_{ij}=q_{ji}$ are established. Also, the quadratic function $f(\boldsymbol{x})$ can be described as follows:
$$
\begin{aligned}
f(\boldsymbol{x})=&
\boldsymbol{x}^{\text{T}}Q\boldsymbol{x}+\boldsymbol{c}^{\text{T}}\boldsymbol{x} \\=&
\sum_{i,j=1}^{n}q_{ij}x_{i}x_{j}+
\sum_{i=1}^{n}c_{i}x_{i} \\=&
\sum_{i=1}^{n}\biggl(
\sum_{j=1}^{n}q_{ij}x_{i}x_{j}+c_{i}x_{i}
\biggr) \\=&
\sum_{i=1}^{n}g(x_{i})
\end{aligned}
$$
where specific functions $g_{i}=g(x_{i})$ are defined:
$$
g(x_{i})=\sum_{j=1}^{n}q_{ij}x_{i}x_{j}+c_{i}x_{i}
$$
Of course, the Boolean vector indicates only binary number so that the function can be divided the following two cases:
$$
g_{i}=
\begin{cases}
\displaystyle
\sum_{j=1}^{n}q_{ij}x_{j}+c_{i} & (x_{i}=1) \\ \\
0 & (x_{i}=0)
\end{cases}
$$
To get the minimized solution, the functions $g_{i}$ must be made to become smaller. Now the condition is set to compare with each cases:
$$
\begin{aligned}
g_{i}(1)<&g_{i}(0) \\
\sum_{j=1}^{n}q_{ij}x_{j}+c_{i}<& \ 0
\end{aligned}
$$ 
Then, when we turn over the one binary parameter by the above condition, all equations must be changed because the a matrix coefficient includes all conditions. For instance, when the $k \ (1\leq k \leq n)$ th function satisfies the above condition and switches "True$=1$" from "False$=0$", the all functions except own  are renew using the following top case. On the other hand, the opposite case as switched "False$=0$" from "True$=1$", the middle equation is used. The otherwise case, it does not need to change the value. Likewise, other functions are applied simultaneously below:
$$
\begin{aligned}
&g_{i\neq k}'=
\begin{cases}
g_{i}+q_{ik} & (x_{k}=0\to 1)\\
g_{i}-q_{ik} & (x_{k}=1\to 0)\\
g_{i}        & (\text{no change})
\end{cases}\\ \\
&g_{i=k}'=
\begin{cases}
g_{k} & (x_{k}=1)\\
0 & (x_{k}=0)
\end{cases}
\end{aligned}
$$
Then these operations are repeated until convergence under finite number of trials
$t$ and can be converted with the matrix and vectors as follows. Then the Boolean vector is decided by the result of logical operation:
$$
\begin{aligned}
\boldsymbol{g}^{t+1}=&Q
\biggl\{\Big(\boldsymbol{x}^t+
(\boldsymbol{g}^{t}<\mathbf{0})-
(\boldsymbol{g}^{t}>\mathbf{0})
\Big)>\mathbf{0}\biggr\}
+\boldsymbol{c} \\=& 
Q(\boldsymbol{g}^{t}<\mathbf{0})+\boldsymbol{c} \\=&
Q\boldsymbol{x}^{t+1}+\boldsymbol{c}
\end{aligned}
$$
where:
$$
\begin{aligned}
\boldsymbol{g}^t=&
\begin{bmatrix}
g_{1}^t & g_{2}^t & \cdots & g_{i}^t & \cdots & g_{n}^t
\end{bmatrix}^{\text{T}} \\=&
Q\boldsymbol{x}^t+\boldsymbol{c}
\end{aligned}
$$
and the logical operation can be simplified owing to the following table:
$$
  \begin{array}{ccc|c}
\hline
    (x_{i}^t) &(g_{i}^{t}<0) & (g_{i}^{t}>0)  & (x_{i}^{t+1}) \\ 
\hline
    1 & 1 & 0 & 1 \\
    1 & 0 & 1 & 0 \\
    0 & 1 & 0 & 1 \\
    0 & 0 & 1 & 0 \\
\hline
  \end{array}
\Longrightarrow
  \begin{array}{c|c}
\hline
(g_{i}^{t}<0) & (x_{i}^{t+1}) \\ 
\hline
     1 &  1 \\
     0 &  0 \\
     1 &  1 \\
     0 &  0 \\
\hline
  \end{array}
$$
Then, the initial values is set $\boldsymbol{x}^{t=0}=(\boldsymbol{c}<\mathbf{0})$ because it is ensured that $\boldsymbol{c}^{\text{T}}\boldsymbol{x}^{t=0}$ is indicated negative. Herewith, it is easy to converge rapidly. 
2, Numerical experiment
An arbitrary real symmetric matrix and a vector are set when the size $n=8$:

$$
Q=
\begin{bmatrix}
16 & -2 & -8 & -12 & 7 & -2 & -2 & 1 \\
 & -10 & 25 & 3 & -4 & -13 & 22 & -19 \\
 &  & 7 & -8 & -14 & -15 & -4 & -25 \\
 &  &  & -5 & -20 & 8 & 8 & 10 \\
 &  &  &  & 18 & 7 & -10 & 4 \\
 &  &  &  &  & 5 & 11 & -12 \\
 &  &  &  &  &  & -2 & 15 \\
 & & & & & & & 12 
\end{bmatrix}
, \ \ \ \ 
\boldsymbol{c}=
\begin{bmatrix}
-1 \\ -11 \\ 7 \\ -7 \\ 28 \\ 9 \\ 3 \\ -10
\end{bmatrix}
$$
Then $t=3$, the minimum value was found on $f(\boldsymbol{x}^{t=3})=-116$ and the combination of Boolean vector was shown below:
$$
\boldsymbol{x}^{t=3}=
\begin{bmatrix}
1 & 1 & 1 & 0 & 0 & 1 & 0 & 1
\end{bmatrix}^{\text{T}}
$$
Next, we attempt a large case as $n=2^8$. Generally, it is impossible to find the minimum value due to numerous number of combination ($1.158\times 10^{77}$). However we can see the below figure which is described that the minimum value is discovered on the number of trial $t=18$. 

