The quantum query complexity of approximating the median and related statistics
The quantum query complexity of approximating the median and related statistics
复制标题
DOI：
10.1145/301250.301349
复制
发表时间：
1998-04
期刊：
影响因子：
--
通讯作者：
A. Nayak;Felix Wu
中科院分区：
文献类型：
--
作者：
A. Nayak;Felix Wu
令X = （x_0，…），x_{n-1})$是n个数字的序列。对于\epsilon > 0，如果严格小于x_i的元素数量和严格大于x_i的元素数量都小于（1+\epsilon）n/2，我们说x_i是一个\epsilon近似中值。我们考虑计算一个\epsilon-近似中值的量子查询复杂性，给定序列X作为一个oracle。我们证明了对于任何计算概率大于1/2的\epsilon-近似中值的量子算法的\Omega（\min{{1/\epsilon},n}）查询的下界。我们还展示了如何使用O({1/\epsilon}\log({1\/\epsilon}) \log\log({1/\epsilon})) oracle查询来计算\epsilon-approximate median，这代表了由于Grover而对早期算法的改进。因此，我们得到的下界基本上是最优的。在比较树模型中，上界和下界同样成立。我们的下界结果是最近由Beals等人引入量子复杂性理论的多项式范式的一个应用。该证明的主要内容是“近似”对称部分布尔函数的实多线性多项式的多项式次下界。度界扩展了Paturi的结果，并立即给出了逼近第k个最小元素、逼近数列均值以及近似计算布尔函数中1的个数等问题的下界。所有得到的边界都在最优的多对数因子范围内（正如我们所展示的，没有已知的最优或接近最优算法的算法），从而证明了多项式方法的力量。
Let X = (x_0,...,x_{n-1})$ be a sequence of n numbers. For \epsilon > 0, we say that x_i is an \epsilon-approximate median if the number of elements strictly less than x_i, and the number of elements strictly greater than x_i are each less than (1+\epsilon)n/2. We consider the quantum query complexity of computing an \epsilon-approximate median, given the sequence X as an oracle. We prove a lower bound of \Omega(\min{{1/\epsilon},n}) queries for any quantum algorithm that computes an \epsilon-approximate median with any constant probability greater than 1/2. We also show how an \epsilon-approximate median may be computed with O({1/\epsilon}\log({1\/\epsilon}) \log\log({1/\epsilon})) oracle queries, which represents an improvement over an earlier algorithm due to Grover. Thus, the lower bound we obtain is essentially optimal. The upper and the lower bound both hold in the comparison tree model as well. Our lower bound result is an application of the polynomial paradigm recently introduced to quantum complexity theory by Beals et al. The main ingredient in the proof is a polynomial degree lower bound for real multilinear polynomials that ``approximate'' symmetric partial boolean functions. The degree bound extends a result of Paturi and also immediately yields lower bounds for the problems of approximating the kth-smallest element, approximating the mean of a sequence of numbers, and that of approximately counting the number of ones of a boolean function. All bounds obtained come within polylogarithmic factors of the optimal (as we show by presenting algorithms where no such optimal or near optimal algorithms were known), thus demonstrating the power of the polynomial method.