[CS] Roozbeh Bassirianjahromi Candidacy Exam/Apr 3, 2025

[via cs]

This is an announcement of Roozbeh Bassirianjahromi's Candidacy Exam.
===============================================
Candidate: Roozbeh Bassirianjahromi

Date: Thursday, April 03, 2025

Time: 12 pm CST

Location: JCL 298

Title: Quantum Merlin-Arthur and proofs without relative phase

Abstract: We study a variant of QMA where quantum proofs have no relative phase (i.e. non-negative amplitudes, up to a global phase). If only completeness is modified, this class is equal to QMA [arXiv:1410.2882]; but if both completeness and soundness are modified, the class (named QMA+ by Jeronimo and Wu) can be much more powerful. We show that QMA+ with some constant gap is equal to NEXP, yet QMA+ with some *other* constant gap is equal to QMA. One interpretation is that Merlin's ability to "deceive" originates from relative phase at least as much as from entanglement, since QMA(2) $\subseteq$ NEXP

Advisors: Bill Fefferman

Committee Members: Aaron Potechin, Bill Fefferman, and Liang Jiang