|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
The quantum query complexity of approximating the median and related statistics | | Ashwin Nayak
; Felix Wu
; | | Date: |
29 Apr 1998 | | Subject: | Quantum Physics; Computational Complexity | quant-ph cs.CC | | Abstract: | 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}) loglog({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. | | Source: | arXiv, quant-ph/9804066 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER