首页    期刊浏览 2025年02月21日 星期五
登录注册

文章基本信息

  • 标题:A Super-Grover Separation Between Randomized and Quantum Query Complexities
  • 本地全文:下载
  • 作者:Shalev Ben-David
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2015
  • 卷号:2015
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We construct a total Boolean function f satisfying R ( f ) = ( Q ( f ) 5 2 ) , refuting the long-standing conjecture that R ( f ) = O ( Q ( f ) 2 ) for all total Boolean functions. Assuming a conjecture of Aaronson and Ambainis about optimal quantum speedups for partial functions, we improve this to R ( f ) = ( Q ( f ) 3 ) . Our construction is motivated by the Göös-Pitassi-Watson function but does not use it.

  • 关键词:decision tree complexity ; quantum complexity ; query complexity
国家哲学社会科学文献中心版权所有