cs daily Subj-class mailing 1 1 (fwd)

[Kragen]

What does this mean?  It looks like it might mean that quantum
computation might speed up a lot more than just factoring big numbers.

-- 
<kragen@pobox.com>       Kragen Sitaker     <http://www.pobox.com/~kragen/>
Irony and sarcasm deflate seriousness, and when your seriousness becomes detum-
escent, you're not held responsible for your thoughts. Irony beats thinking like
rock beats scissors. -- http://www.hyperorg.com/backissues/joho-june2-98.html

---------- Forwarded message ----------
Date: Wed, 18 Nov 1998 05:59:50 -0700 (MST)
From: send mail ONLY to cs <no-reply@xxx.lanl.gov>
Reply-To: cs@xxx.lanl.gov
To: cs daily title/abstract distribution <rabble@xxx.lanl.gov>
Subject: cs daily Subj-class mailing 1 1

------------------------------------------------------------------------------
------------------------------------------------------------------------------
send mail only to cs@xxx.lanl.gov, do not reply to no-reply@...
send any complaints regarding submissions directly to submitter.
use a single `get' to request multiple papers, `list macros' for available
macro packages, and `help' for a list of available commands and other info.
------------------------------------------------------------------------------
point your www client at http://xxx.lanl.gov/
------------------------------------------------------------------------------
 Submissions to:
Computational Complexity
 received from  Tue 17 Nov 98 01:00:05 GMT  to  Wed 18 Nov 98 01:00:02 GMT
------------------------------------------------------------------------------
%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-
------------------------------------------------------------------------------
\\
Paper (*cross-listing*): quant-ph/9804066
From: Ashwin Nayak <ashwin@cs.berkeley.edu>
Date: Wed, 29 Apr 1998 02:00:07 GMT   (6kb)
Date (revised v2): Sun, 15 Nov 1998 01:36:43 GMT   (21kb)

Title: The quantum query complexity of approximating the median and related
  statistics
Authors: Ashwin Nayak, Felix Wu
Comments: 20 pages. Preliminary draft. Extends results of previous version to
  several other problems, and gives some new upper bounds
Subj-class: Quantum Physics; Computational Complexity
\\
  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.
\\ ( http://xxx.lanl.gov/abs/quant-ph/9804066 ,  21kb)
%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%--%%
%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---%%%---