Disturbed witnesses in quantum complexity theory

Abstract

QMA is the complexity class of computational problems that are efficiently verifiable by a quantum algorithm with the help of a witness in contrast to the smaller class BQP of problems efficiently solvable by a quantum algorithm without a witness. Like their classical counterparts NP and P, the class QMA is believed to be strictly larger than BQP, but the definitive answer remains one of the most fundamental open problems of complexity theory. An equality of QMA and BQP would imply that quantum computers can solve many physically and logically relevant problems efficiently, including the Local Hamiltonian problem and the Satisfiability problem for Boolean formulas. New approaches to gain more insight into the structure of BQP and QMA as well as which witness forms are sufficient for QMA are hence worth pursuing. This thesis comprises three research focuses: Firstly, we extend the uniform diagonalization theorem to complexity classes of promise problems in order to construct strictly intermediate problems between QMA and BQP under the assumption that these classes are unequal. The existence of strictly intermediate problems motivates our definition of noisy QMA classes, which form hierarchies of intermediate classes between QMA and BQP by restricting the witnesses to outputs of certain quantum channels. In our second research focus we apply the tool of concatenated coding to prove a bound on the witness noise up to which QMA stays robust. Besides a bound for general i.i.d. channels, we can prove that QMA stays robust if each witness qubit is disturbed by 18 % depolarizing or 27 % dephasing noise, while for complete depolarization or dephasing the noisy class obviously collapses to BQP and QCMA, respectively. In the third research focus we interpret the famous QPCP conjecture as robustness of the class QMA against high witness disturbance. Moreover, we consider a multiprover protocol by Fitzsimons and Vidick that constitutes a first step towards an important alternative formulation of the QPCP conjecture and achieve a reduction of the number of provers and an improvement of the acceptance probability for this protocol.