  We consider coGapSVP_\sqrt{n}, a gap version of the shortest vector in a
lattice problem. This problem is known to be in AM\cap coNP but is not known to
be in NP or in MA. We prove that it lies inside QMA, the quantum analogue of
NP. This is the first non-trivial upper bound on the quantum complexity of a
lattice problem.
  The proof relies on two novel ideas. First, we give a new characterization of
QMA, called QMA+. Working with the QMA+ formulation allows us to circumvent a
problem which arises commonly in the context of QMA: the prover might use
entanglement between different copies of the same state in order to cheat. The
second idea involves using estimations of autocorrelation functions for
verification. We make the important observation that autocorrelation functions
are positive definite functions and using properties of such functions we
severely restrict the prover's possibility to cheat. We hope that these ideas
will lead to further developments in the field.
