The Living StoqMA Page
The introduction of the theory of quantum computation has added many new questions in complexity which may have not risen naturally in the classical realm. Many who study quantum computing may encounter the classes without reference to their source, and be quite confused to why such definitions are necessary or even arose in the first place. However, when examined more closely, we find that the sources of these classes are quite natural questions to ask about quantum computation, and known results and hypotheses give new ways to understand these questions. StoqMA is one such class, whose definition as a complexity class looks quite nonsensical at first, but has led to answering some interesting questions about quantum computing and complexity theory.
Definition
The class StoqMA is defined by the use of a stoquastic verifier. A stoquastic verifier is a verifier which can be modeled as a classical reversible circuit, which is a essentially a quantum circuit that only uses X, CNOT, and Toffoli gates. The verifier takes as input a classical string \(x\) along with a quantum witness which are passed to the circuit.
A stoquastic verifier is a tuple \(V = (n, n_w, n_0, n_+, U)\), where \(n\) is the number of input bits, \(n_w\) the number of input witness qubits, \(n_0\) the number of input auxiliary qubits \(\ket{0}\), \(n_+\) the number of input auxiliary qubits \(\ket{+}\) and \(U\) is a quantum circuit on \(n + n_w + n_0 + n_+\) qubits with NOT, CNOT, and Toffoli gates (classical reversible circuit). The acceptance probability of a stoquastic verifier \(V\) on input string \(x \in \{0, 1\}^n\) and \(n_w\)-qubit witness state \(\ket{\psi}\) is defined as \(\text{Pr}[V \text{ accepts } (x, \ket{\psi})] = \bra{\psi_{in}}U^\dagger \Pi_{out} U \ket{\psi_{in}}\). Here, \(\ket{\psi_{in}} = \ket{x} \otimes \ket{\psi} \otimes \ket{0}^{\otimes n_0} \otimes \ket{+}^{\otimes n_+}\) is the initial state and \(\Pi_{out} = \ket{+}\bra{+}_1 \otimes I_{else}\) projects the first qubit onto the state \(\ket{+}\).
A promise problem \(L = (L_{yes}, L_{no}) \in {StoqMA}(a,b)\) iff there exists a uniform family of stoquastic verifiers, such that for any fixed number of input bits \(n\) the corresponding verifier \(V\) uses at most \(p_1(n)\) qubits, \(p_2(n)\) gates where both \(p_1\) and \(p_2\) are polynomials; and obeys the following: - Completeness: If \(x \in L_{yes}\), then there is some \(\ket{\psi}\) s.t. \(\text{Pr}[V \text{ accepts } (x, \ket{\psi})] \geq a\); - Soundness: If \(x \in L_{no}\), then for any \(\ket{\psi}\), \(\text{Pr}[V \text{ accepts } (x, \ket{\psi})] \leq b\).