Merlin-Arthur Games and Stoquastic Complexity

Simple item page
dc.creatorBravyi, Sergey
dc.creatorBessen, Arvid J.
dc.creatorTerhal, Barbara M.
dc.date2006-11-02
dc.date2006-12-19
dc.date.accessioned2026-07-07T07:36:09Z
dc.date.available2026-07-07T07:36:09Z
dc.descriptionMA 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.
dc.description20 pages, 2 figures (proof of AM-hardness is simplified in Section 5)
dc.identifierhttps://arxiv.org/abs/quant-ph/0611021
dc.identifierhttp://arxiv.org/abs/quant-ph/0611021
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/120329
dc.subjectQuantum Physics
dc.subjectComputational Complexity
dc.titleMerlin-Arthur Games and Stoquastic Complexity
dc.typetext

Files

Collections

arXiv