Considering the problem of finding lattice points $(x_1, x_2 ... x_n)$ that satisfy a quadratic law:

$F(x_1, x_2... x_n) = 0$

such that $F(x_1, x_2... x_n)$ is a second degree polynomial

It is known that for some simple examples such as:

$x_1^2 + x_2^2 = x_3^2$ (pythagorean rule)

$x_1x_2 = N$ (factorization of integers)

the problem can be solved in polynomial time on a classical or quantum machine. Is it possible that in general all single equation quadratic diophantine equations can be solved in polynomial time on a Quantum Machine? Is there any strong counterexample or example that sets serious doubt?

  • $\begingroup$ You mean finding one lattice point, or all lattice points? I doubt you can find all lattice points of $x_1^2+x_2^2=x_3^2$ in polynomial time :) $\endgroup$ – Thomas Andrews Jun 26 '13 at 17:39
  • $\begingroup$ a lattice point. But would it be out of the question to find a general rule for all lattice points? The pythagorean triple does have a general rule involving only 2 variables. $\endgroup$ – frogeyedpeas Jun 26 '13 at 17:43
  • $\begingroup$ There is certainly a lot that you can do with homogeneous quadratic polynomials, but I'm not sure there is a speedy way in general to, for example, determine if $x^2-Ny^2=-1$ has a solution? (There is an algorithm, but I think it can take a fair amount of time in terms of $N$.) Also, when you say "polynomial time," polynomial against what variable(s)? $\endgroup$ – Thomas Andrews Jun 26 '13 at 18:01
  • $\begingroup$ polynomial with respect to the "size" (number of bits) used to represent the coefficients $\endgroup$ – frogeyedpeas Jun 26 '13 at 18:03
  • $\begingroup$ If it is in terms of bits, then it is unknown whether $xy=N$ can be (generally) solved in polynomial time by a classic Turing machine. You can, of course, come up with the individual answer, $(x,y)=(1,N)$, but I think it is unknown otherwise. $\endgroup$ – Thomas Andrews Jun 26 '13 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.