I am given a $n \times n$ matrix $A$ with real entries and define the inner product $$\langle x,y\rangle = x^T A y.$$
I am also given an integer $k$ and need to find all binary vectors $x$ such that $\langle x,x \rangle = k.$
By binary vector I mean a vector whose entries are in $\{0,1\}.$ For $n$ small it is not hard to solve this problem - simply test all possible $2^n$ vectors. In practice $n$ can be quite large and there is only a small fraction of vectors that satisfy this condition. Hence I am wondering
Is there a more efficient way to compute all binary vectors satisfying $\langle x,x \rangle = k$?
I am pretty sure this problem is hard in general but I am wondering if there is any way to get away with having to test all $2^n$ vectors?
Edit. The matrix $A$ is of the form $(\lambda I-B)^{-1}$ where $\lambda$ is an integer and $B$ is a binary symmetric matrix. $\lambda$ is not an eigenvalue of $B.$