I'm not sure if I phrased the question correctly, but let's say that due to a result called 15 theorem that "if a positive definite quadratic form with integer matrix represents all positive integers up to $15$, the it represents all positive integers". As I'm new to the theory of quadratic forms (I only read, partially, the first lecture of "THE SENSUAL (quadratic) FORM" by Conway and Fung), I'm interested by the question of checking whether an integer value is retrieved as a result of a quadratic form.
More formally, for any fixed $n \in \mathbb{N}^*$, given $A \in \mathcal{M}_n(\mathbb{Z})$ positive definite and $k \in \mathbb{N}$, is there a general algorithm to find (or decide whether there exists) $x \in \mathcal{M}_{n \times 1}(\mathbb{R})$ such that $x^T A x = k$?
Correct me if I'm wrong, but from a "numerical" point of view, I think one can find the roots of the multivariate polynomial $E(x) = x^T A x - k$, and check for each root whether it is an integer. This may be able to solve using some traditional multivariate polynomial root finding algorithms (which I don't know, and I'm not sure if it works). Is there any algorithm that specifically answer this problem (numerically, algebraically, or combinatorially)?
At first, it looks as if it is an NP problem, since given $x \in \mathcal{M}_{n \times 1}(\mathbb{R})$ (in particular, I'd rather say $\mathcal{M}_{n \times 1}(\mathbb{Q})$ instead), one can verify the equation $x^T A x = k$ easily. However, due to something like this (The Uncracked Problem with 33 - Numberphile), I'm afraid that $x$ might be very large, and hence, might contain information bigger than polynomial on $n$.
Edit: To ask for a solution in $\mathbb{R}^n$, this looks like I'm asking the wrong question. Since it is positive definite, I can descend ($\mathbb{R}^n$-wise) the "well" to find the minimum real $m > 0$ representable by the form, then any integer $k \geq m$ is representable by the form at some point in $\mathbb{R}^n$ due to continuity and unboundedness of the form. So maybe the interesting question is to find solutions in $\mathbb{Q}^n$ or $\mathbb{Z}^n$. Note that I also found this Wikipedia article on Hilbert's 11th problem, which I haven't yet understood it completely. Further explanations are appreciated.
Edit 2. No. The original "descend the well" algorithm only works on integral binary quadratic forms, but in this case the interesting question lies on a more general setting of multivariate (more than 2 variables) quadratic forms. But I guess there should be something that works the same, i.e., some algorithm that gives the minimum real value represented by a quadratic form. Hmm... I don't know.
Edit 3. As suggested by Gerry Myerson, I'm editing this to explicitly state the question as follows:
Problem. For $n \in \mathbb{N}^*$ fixed, given symmetric positive definite $A \in \mathcal{M}_n(\mathbb{Z})$, and given $k \in \mathbb{N}$. Is there a general algorithm to find $x \in K^n$ such that $x^T A x = k$?
Question 0. For $K = \mathbb{R}$ (answered by Gerry Myerson in the comments)
Question 1. For $K = \mathbb{Q}$.
Question 2. For $K = \mathbb{Z}$.