The Need for Structure in Quantum Speedups

Details The Need for Structure in Quantum Speedups The Need for Structure in Quantum Speedups

2009-11-05

arxiv.org/abs/0911.0996v1

Physics

Quantum Physics

23 pages

Scientific paper

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate. First, we show that for any problem that is invariant under permuting inputs and outputs (like the collision or the element distinctness problems), the quantum query complexity is at least the 9th root of the classical randomized query complexity. This resolves a conjecture of Watrous from 2002. Second, inspired by recent work of O'Donnell et al. and Dinur et al., we conjecture that every bounded low-degree polynomial has a "highly influential" variable. Assuming this conjecture, we show that every T-query quantum algorithm can be simulated on most inputs by a poly(T)-query classical algorithm, and that one essentially cannot hope to prove P!=BQP relative to a random oracle.

Affiliated with

Also associated with

No associations

Rating

The Need for Structure in Quantum Speedups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Need for Structure in Quantum Speedups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Need for Structure in Quantum Speedups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-417864