IQI Weekly Seminar

  How much computational power does an efficient quantum verifier gain  when given a polynomial size quantum state to support the validity of  a mathematical claim?  In particular, is there some problem that can  be solved efficiently in this model, that cannot be solved if the  verifier was instead given a classical bitstring?  This question, the  so-called QMA vs QCMA problem, is fundamental in quantum complexity  theory.  To complexity theorists, the question can be motivated simply  by trying to understand the power of quantum nondeterminism, where  both QMA and QCMA can by seen as ``quantum analogues'' of NP.  More  physically, QMA is characterized by the k-local Hamiltonian problem,  in which we are asked to decide if the ground state energy of a local  Hamiltonian is above or below a specified threshold.  In this setting,  the QMA vs QCMA question can be rephrased as asking whether or not  there exists a purely classical description of the ground state that  allows us to make this decision.    Despite the importance of this question, little has been proven.  Even  finding an oracle separation has resisted progress.  In this talk we  will make progress this question and augment the work of Aaronson and  Kuperberg in 2006, where a nonstandard "quantum oracle" separation was  proven.    Joint work with Shelby Kimmel (QuICS, UMD/NIST)