Class Description

cq-Σ2: Classical-Quantum-Σ2P

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?

Linked From

No class.