A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs
A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs
复制标题
一种新的量子下界方法，应用于直接乘积定理和时空权衡
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
R. D. Wolf
中科院分区：
文献类型：
--
作者：
A. Ambainis;R. Spalek;R. D. Wolf
摘要
我们给出了一个新版本的对手的方法证明量子查询算法的下界。新方法是基于分析的特征空间结构的问题在手。我们用它来证明一个新的和最佳的强直积定理的双边错误量子算法计算k个独立的对称布尔函数的实例：如果该算法使用显着小于k倍的查询所需的函数的一个实例，那么它的成功概率是指数小的k。我们还使用多项式的方法来证明一个直积定理的单侧误差算法的k阈值函数的成功概率上的一个更强的界。最后，我们提出了一个量子算法来评估线性不等式系统的解决方案，并使用我们的直积定理表明，该算法的时空权衡接近最优。
Abstract
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.