Stoquastic circuit

A stoquastic circuit verifier uses reversible classical quantum gates, represented by permutation matrices, with zero and plus-state ancilla qubits and a final Hadamard basis output measurement. A basis input remains an entrywise nonnegative state; a general quantum witness need not be a basis input. The resulting acceptance structure is used in StoqMA.

If the output of a stoquastic circuit is $|0⟩|r_0⟩+|1⟩|r_1⟩$ with nonnegative amplitudes, its plus-outcome probability is $1/2+\mathrm{Re}⟨r_0|r_1⟩\ge 1/2$. Basis quantum witnesses with zero and plus ancilla qubits always have this property. A soundness threshold below one half cannot hold for every such input.