首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:Improved Soundness for QMA with Multiple Provers
  • 本地全文:下载
  • 作者:Alessandro Chiesa ; Michael A. Forbes
  • 期刊名称:Chicago Journal of Theoretical Computer Science
  • 印刷版ISSN:1073-0486
  • 出版年度:2013
  • 卷号:2013
  • 出版社:MIT Press ; University of Chicago, Department of Computer Science
  • 摘要:

    We present three contributions to the understanding of QMAs with multiple provers :We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM 2009], yielding a soundness gap $\Omega(N^{-2})$. Our improvement is achieved without the use of an instance w ith a constant soundness gap (i.e., without using a ``PCP''). We give a tight soundness analysis of the protocol of [Chen and Drucker, ArXiV 2010], thereby improving their result from a ``monolithic'' protocol where $\Theta(\sqrt{N})$ provers are needed in order to have any soundness gap, to a protocol with a smooth trade-off between the number of provers $\kappa$ and a soundness gap $\Omega(\kappa^{2}N^{-1})$, as long as $\kappa \in \Omega(\log N)$. (And, when $\kappa \in \Omega(\log N)$, we recover the original parameters of Chen and Drucker.) We make progress towards an open question of [Aaronson et al., ToC 2009] about what kinds of NP-complete problems are amenable to ``sublinear'' multiple-prover QMA protocols, by observing that a large class of such examples can easily be derived from results already in the PCP literature --- namely, at least the languages recognized by a non-deterministic RAMs in quasilinear time.

国家哲学社会科学文献中心版权所有