{
  "annotation_id": "c58c89c7-dc56-4af8-b7e0-d76776a75ff5",
  "date_created": "2026-03-02T18:01:59.930000Z",
  "date_modified": "2026-03-02T18:01:59.930000Z",
  "file_hash": "576680d346af4bd3e57d3ddc81a988598924d6df4968a7f650ee8a9f792ae7a6",
  "private": false,
  "record": {
    "abstract": "We consider coGapSVP_\\sqrt{n}, a gap version of the shortest vector in a\nlattice problem. This problem is known to be in AM\\cap coNP but is not known to\nbe in NP or in MA. We prove that it lies inside QMA, the quantum analogue of\nNP. This is the first non-trivial upper bound on the quantum complexity of a\nlattice problem.\n  The proof relies on two novel ideas. First, we give a new characterization of\nQMA, called QMA+. Working with the QMA+ formulation allows us to circumvent a\nproblem which arises commonly in the context of QMA: the prover might use\nentanglement between different copies of the same state in order to cheat. The\nsecond idea involves using estimations of autocorrelation functions for\nverification. We make the important observation that autocorrelation functions\nare positive definite functions and using properties of such functions we\nseverely restrict the prover\u0027s possibility to cheat. We hope that these ideas\nwill lead to further developments in the field.",
    "arxiv_id": "quant-ph/0307220",
    "authors": [
      "Dorit Aharonov",
      "Oded Regev"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "A Lattice Problem in Quantum NP",
    "url": "https://arxiv.org/abs/quant-ph/0307220"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "6363467c-bb5b-4b24-a21e-9a6701e335c8",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}