Consider the following quadratic maximization: \begin{align} \max_{\mathbf{x} \in \mathcal{X}} &\quad\mathbf{x}^{T}\mathbf{A}\mathbf{x} \end{align} with \begin{align} \mathcal{X} = \lbrace \mathbf{x} \in \mathbb{R}^{n} :~ \|\mathbf{x}\|_{2}=1, \|\mathbf{x}\|_{0}\le k \rbrace, \end{align} where $\mathbf{A}$ is a positive semidefinite matrix and $k \le n$ is a sparsity parameter. This problem is NP-hard, by a reduction from the max-clique problem.
I am interested in a similar problem obtained by imposing additional structure on $\mathcal{X}$. In particular, assume that the $n$ variables in $\mathbf{x}$ are partitioned into $k$ disjoint groups. We restrict the feasible set to unit-length vectors $\mathbf{x}$ with one active variable per group. That is, $\mathcal{X}$ contains again $k$-sparse vectors, but the support cannot be arbitrary; it contains (at most) one nonzero entry for each of the $k$ groups.
Note that the feasible set in the modified problem is a subset of the previous maximization, but the number of feasible supports can still be exponential in the number of variables $n$ (for appropriately chosen $k$).
I suspect that the modified problem is also NP-hard. Any ideas on how to show that (or disprove)? Feel free to share your intuition.