A bounded-error quantum generalization of Σ2P in which the first proof is classical, the second proof quantum, and the verifier is a quantum circuit.
Defined in [GK14].
The following problems are complete for cq-Σ2 (the first two are, in addition, strongly hard to approximate for cq-Σ2) [GK14]:QUANTUM SUCCINCT SET COVER, QUANTUM IRREDUNDANT, cq-Σ2LH (a quantum generalization of the canonical Σ2P-complete problem ΣiSAT). The first of these roughly asks: Given a frustrated local Hamiltonian, what is the maximum number of local interaction terms which can be discarded before the resulting Hamiltonian is no longer frustrated?
No class.