首页> 外文期刊>Algorithmica >A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs
【24h】

A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs

机译:一种新的量子下界方法,应用于直接乘积定理和时空权衡

获取原文
获取原文并翻译 | 示例

摘要

We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal.
机译:我们给出了一种新的对手方法,以证明量子查询算法的下界。新方法是基于分析当前问题的本征空间结构。我们用它证明了计算对称布尔函数的k个独立实例的2面误差量子算法的一种新的和最佳的强直接乘积定理:如果该算法使用的查询次数显着少于该函数一个实例所需查询次数的k倍,则其成功概率在k中呈指数减小。我们还使用多项式方法证明了针对k个阈值函数的一面错误算法的直接乘积定理,其成功概率的界限更强。最后,我们提出了一种用于评估线性不等式系统解的量子算法,并使用我们的直接乘积定理表明该算法的时空折衷接近最优。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号