Approximation of a quadratic form

Question

Let $\mathbf{x}=(x_1,\cdots,x_n)^T\in\mathbb{R}^n$ and $A\in\mathbb{S}_{++}^n$ be a symmetric positive definite matrix. Also, let $Q\colon\mathbb{R}^n\to\mathbb{R}$ be the quadratic form given by $$ Q(\mathbf{x})=\mathbf{x}^TA\mathbf{x}. $$ By definition, the above quadratic form can be computed using the double sum, $$ Q(\mathbf{x}) = \sum_{i,j=1}^n A_{ij}x_ix_j, $$ which is expensive for my purposes... Could anyone suggest any approximation that may be executed faster than $\mathcal{O}(n^2)$? Thanks!