I have the equation $ \mathbf{x}^T A \mathbf{x} = b $, where $b$ is a scalar, $\mathbf{x}$ a vector of size $M$, and A a matrix of size $M\times M$. $b$ and $\mathbf{x}$ are given.
How many such equations do I need to find the (common) $A$, and how do I do it?
First, you can only find the symmetric part of $A$, since $x^TAx=x^TA^Tx$.
So let us say that $A$ is already symmetric. A symmetric matrix has $\frac12M(M+1)$ degrees of freedom, so you need at least that many equations.
Now let $e_j$ be the $j$th natural basis vector, and note that $e_j^TAe_j=a_{jj}$, while $(e_j+e_k)^TA(e_j+e_k)=a_{jj}+2a_{jk}+a_{kk}$. I have now named $\frac12M(M+1)$ vektors (all $e_j$, and all $e_j+e_k$ with $j<k$) sufficient to let you determine $A$ from the given equations.
PS. You may wonder what it takes for an arbitrary set of $\frac12M(M+1)$ vektors $x$ to be sufficient. One answer comes from noting that $x^TAx=\operatorname{tr}(xx^TA)$, and noting that $\langle A,B\rangle=\operatorname{tr}(B^TA)$ is an inner product on the space of symmetric matrices, the answer is that all the matrices $xx^T$ must be linearly independent.