StoqMA is a restricted quantum-verifier class using stoquastic circuits and polynomial-size quantum witnesses. A YES instance has a quantum witness accepted with probability at least ; on a NO instance every quantum witness has acceptance at most , with an inverse-polynomial gap . An optimal quantum witness can be chosen with nonnegative amplitudes, since the witness acceptance operator is entrywise nonnegative. The quantum witness is generally a superposition, rather than a computational basis vector. The stoquastic acceptance floor explains the lower limit for a nontrivial soundness promise.
Articles by others on the same topic
There are currently no matching articles.