首页    期刊浏览 2025年12月04日 星期四
登录注册

文章基本信息

  • 标题:On Quantum Interactive Proofs with Short Messages
  • 本地全文:下载
  • 作者:Attila Pereszlényi
  • 期刊名称:Chicago Journal of Theoretical Computer Science
  • 印刷版ISSN:1073-0486
  • 出版年度:2012
  • 卷号:2012
  • 出版社:MIT Press ; University of Chicago, Department of Computer Science
  • 摘要:

    This paper proves one of the open problems posed by Beigi, Shor and Watrous in Theory of Computing volume 7, article 7, pp. 101-117 (2011). We consider quantum interactive proof systems where, in the beginning, the verifier and prover send messages to each other, with the combined length of all messages being at most logarithmic (in the input length); and at the end, the prover sends a polynomial-length message to the verifier. We show that this class has the same expressive power as QMA.

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