Class Description

StoqMA: Stoquastic MA

The class of decision problems solvable by a Merlin-Arthur protocol, which goes as follows. Merlin is an unbounded computational entity and Arthur is a polynomial-sized stoquastic verifier, who can construct quantum circuits comprised of gates from the set ${\displaystyle \{X,CX,CCX\}}$ with ancillae qubits prepared in the ${\displaystyle |0\rangle }$ and ${\displaystyle |+\rangle }$ state, with a final measurement in the Hadamard basis. Merlin sends Arthur a polynomial-size proof such that:

1. If the answer is "yes”, then there exists a proof such that Arthur accepts with probability at least ${\displaystyle \alpha }$.
2. If the answer is "no”, then for all proofs Arthur accepts with probability at most ${\displaystyle \beta }$,

where ${\displaystyle 1/2\leq \beta <\alpha \leq 1}$ and ${\displaystyle \alpha -\beta =\Omega (1/{\text{poly}})}$.

Defined in [BBT07], where it is also shown that 2-local stoquastic Hamiltonian problem is complete for the class StoqMA.

It was also shown in [BH16] that the transverse field Ising model is complete for the class StoqMA.

There is no known strong error reduction for StoqMA [AGL21]. It is conjectured that StoqMA with strong error reduction is equivalent to MA [AGL21].

Linked From 0 Classes

No class.