What are some efficient algorithms for determining if a quadratic multivariate polynomial has a solution?
You can decide if a quadratic polynomial $p: \mathbb{R}^n \rightarrow \mathbb{R}$ has real roots with some linear algebra. As you note, the general case should be hard.

Observe first that $p(x) \neq 0$ for all $x \in \mathbb{R}^n$ if either $p(x) &gt; 0$ or $p(x) &lt; 0$ for all $x$ (this follows by continuity). So it is enough to be able to decide if $p(x) &gt; 0$ for all $x$. In general this is related to complexity-theoretic versions of Hilbert's 17th problem: a polynomial $p(x)$ is positive over the reals if and only if you can write $p$ as the sum of squares of rational functions and a positive constant $c$ (this is a theorem by Artin). Finding this decomposition or solving the decision problem is most likely hard in general, but the quadratic case is easy, because of the magic of the spectral theorem. For more information about the general case, look at Devanur,Lipton,Vishnoi, and Monique Laurent's survey.

Let us write $p(x) = p_2(x) + p_1(x) + c$ where $p_2$ is homogeneous of degree 2, $p_1$ is linear, and $c$ is a constant. Let us define $q(x_0,x) = p_2(x) + x_0p_1(x) + cx_0^2$ to be the homogenization of $p$, where $x_0$ is an additional variable. 

Claim. $p(x) &gt; 0 \Leftrightarrow \forall x_0 \neq 0: q(x_0,x) &gt; 0$

The "if" direction is easy. In the non-trivial direction, assume $p(x) &gt; 0$ for all $x$ and assume $x_0 \neq 0$:
$$
q(x_0,x) = x_0^2q\left(1,\frac{x}{x_0}\right) = x_0^2 p\left(\frac{x}{x_0}\right) &gt; 0.
$$
QED

Notice also that, because $q(x_0, x)$ is continuous, if $p(x) &gt; 0$ for all $x$ then $q(x_0,x) \geq 0$ for all $(x_0,x)$ (including $x_0 = 0$).

Since $q$ is homogeneous, we can write $q(x_0,x) = y^TQy$, where $Q$ is a symmetric matrix and $y = (x_0,x)$. By the above, if $p(x) &gt; 0$ for all $x$, then $Q$ is positive semidefinite. Moreover, $q(x_0, x) &gt; 0$ for all $x_0 \neq 0$ if and only if the kernel of $Q$ is a subset of the hyperplane $\{y = (0,x): x \in \mathbb{R}^n\}$. Both these conditions can be decided in polynomial time by computing the SVD of $Q$.