REVIEW 4 cited by
Merlin-Arthur Games and Stoquastic Complexity
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original 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.
Forward citations
Cited by 4 Pith papers
-
The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
StoqMa(k) equals StoqMa for any polynomial k via a positive value-based de Finetti theorem that approximates nonnegative product values with symmetric extensions.
-
The power of unentanglement without destructive interference
StoqMA(2) contains NP with Õ(√n)-qubit proofs and completeness error 2^{-polylog(n)}, is contained in EXP, and satisfies StoqMA(k)=StoqMA(2) for k≥2 when completeness error is negligible.
-
The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
The Guided Local Hamiltonian problem for stoquastic Hamiltonians is promise BPP-hard (even 2-local on lattices), BQP-hard under fixed local constraints, and admits a deterministic classical approximation algorithm whe...
-
Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
New QSAT variants on qubits and qudits are complete for BQP_1, coRP, QCMA and six PI/SoPU classes, implying any classification of strong quantum CSPs must contain at least 13 classes unless some collapse.
Discussion (0). Continue with ORCID to comment.