{
  "annotation_id": "fe865ffb-36c7-4677-a6c0-a5549de2b2e5",
  "date_created": "2026-03-02T18:02:30.563000Z",
  "date_modified": "2026-03-02T18:02:30.563000Z",
  "file_hash": "27afc2390e6154c077e225e9150d78f3c96d081538da3f37c1879e6e303fec30",
  "private": false,
  "record": {
    "abstract": "MA is a class of decision problems for which `yes\u0027-instances have a proof\nthat can be efficiently checked by a classical randomized algorithm. We prove\nthat MA has a natural complete problem which we call the stoquastic k-SAT\nproblem. This is a matrix-valued analogue of the satisfiability problem in\nwhich clauses are k-qubit projectors with non-negative matrix elements, while a\nsatisfying assignment is a vector that belongs to the space spanned by these\nprojectors. Stoquastic k-SAT is the first non-trivial example of a MA-complete\nproblem. We also study the minimum eigenvalue problem for local stoquastic\nHamiltonians that was introduced in quant-ph/0606140, stoquastic LH-MIN. A new\ncomplexity class StoqMA is introduced so that stoquastic LH-MIN is\nStoqMA-complete. Lastly, we consider the average LH-MIN problem for local\nstoquastic Hamiltonians that depend on a random or `quenched disorder\u0027\nparameter, stoquastic AV-LH-MIN. We prove that stoquastic AV-LH-MIN is\ncontained in the complexity class \\AM, the class of decision problems for which\nyes-instances have a randomized interactive proof with two-way communication\nbetween prover and verifier.",
    "arxiv_id": "quant-ph/0611021",
    "authors": [
      "Sergey Bravyi",
      "Arvid J. Bessen",
      "Barbara M. Terhal"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "title": "Merlin-Arthur Games and Stoquastic Complexity",
    "url": "https://arxiv.org/abs/quant-ph/0611021"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "64ef8688-8b21-4b1a-891a-b069d6822c90",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}