dorsal/arxiv
View SchemaMerlin-Arthur Games and Stoquastic Complexity
| Authors | Sergey Bravyi, Arvid J. Bessen, Barbara M. Terhal |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0611021 |
| URL | https://arxiv.org/abs/quant-ph/0611021 |
Abstract
MA is a class of decision problems for which `yes'-instances have a proof that can be efficiently checked by a classical randomized algorithm. We prove that MA has a natural complete problem which we call the stoquastic k-SAT problem. This is a matrix-valued analogue of the satisfiability problem in which clauses are k-qubit projectors with non-negative matrix elements, while a satisfying assignment is a vector that belongs to the space spanned by these projectors. Stoquastic k-SAT is the first non-trivial example of a MA-complete problem. We also study the minimum eigenvalue problem for local stoquastic Hamiltonians that was introduced in quant-ph/0606140, stoquastic LH-MIN. A new complexity class StoqMA is introduced so that stoquastic LH-MIN is StoqMA-complete. Lastly, we consider the average LH-MIN problem for local stoquastic Hamiltonians that depend on a random or `quenched disorder' parameter, stoquastic AV-LH-MIN. We prove that stoquastic AV-LH-MIN is contained in the complexity class \AM, the class of decision problems for which yes-instances have a randomized interactive proof with two-way communication between prover and verifier.
{
"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
}