Quantum proof systems with unentangled provers (QPUP)

• Applicant: Professor Dr. Sevag Gharibian
• Subject Area: Theoretical Computer Science
• Term: since 2026
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 572703436

The complexity class NP has played a foundational role in our characterization of the inherent difficulty of computational problems. Specifically, NP consists of all computational problems with a YES or NO answer, for which if the answer is YES, then there exists an efficiently verifiable proof of this fact. In the quantum setting, the quantum generalization of NP has played a similarly important role. In the canonical definition of quantum NP, known as Quantum Merlin-Arthur (QMA), the proof is now a quantum state and the verifier a polynomial-size quantum circuit. Much is nowadays known about QMA, including bounds on its power, and that it captures the complexity of the physically motivated generalization of the Boolean Satisfiability problem, the Local Hamiltonian problem. In the quantum setting, however, there is a uniquely quantum phenomenon which can be added to a QMA proof system - that of "unentanglement". Roughly, in contrast to classical proof systems, in the quantum world an n qubit state can be entangled, i.e. highly correlated in a non-classical manner. We say a quantum proof system is "unentangled" if the prover is promised to send a state v on 2n qubits, the first n (respectively, last n) of which are entangled amongst themselves, but with no entanglement across the bipartition between the first n qubits versus the last n qubits. The resulting class is known as QMA(2), and is generally believed stronger than QMA. Indeed, it possesses remarkable properties not known to hold for QMA, such as exponential compression of classical proofs. However, the known bounds on the power of QMA(2) remain essentially the trivial ones, QMA (lower bound) and NEXP (upper bound). This proposal aims to conduct a thorough study of the power of QMA(2). Specifically, it targets three directions: (1) Classical proof compression, (2) variants of QMA(2), and (3) sharper bounds on the power of QMA(2). The first will delve deeper into understanding the limits of unentanglement in capturing classical proof systems - for example, can QMA(2) capture interactive proofs with messages sent back and forth? The second will study how varying the definition of QMA(2), such as restricting the verifier's gate set or adding an additional universally quantified proof, changes the class' power. Finally, the third aims to improve the known lower and upper bounds on QMA(2), by (for example) showing that QMA(2) contains the complexity class co-NP.

• DFG Programme: Research Grants