Lower bounds in the quantum cell probe model

Details Lower bounds in the quantum cell probe model Lower bounds in the quantum cell probe model

2001-04-19

arxiv.org/abs/quant-ph/0104100v2

Physics

Quantum Physics

32 pages. A preliminary version appeared at ICALP 2001. This version is substantially revised and expanded. It has new and str

Scientific paper

We introduce a new model for studying quantum data structure problems -- the "quantum cell probe model". We prove a lower bound for the static predecessor problem in the address-only version of this model where we allow quantum parallelism only over the `address lines' of the queries. The address-only quantum cell probe model subsumes the classical cell probe model, and many quantum query algorithms like Grover's algorithm fall into this framework. Our lower bound improves the previous known lower bound for the predecessor problem in the classical cell probe model with randomised query schemes, and matches the classical deterministic upper bound of Beame and Fich. Beame and Fich have also proved a matching lower bound for the predecessor problem, but only in the classical deterministic setting. Our lower bound has the advantage that it holds for the more general quantum model, and also, its proof is substantially simpler than that of Beame and Fich. We prove our lower bound by obtaining a round elimination lemma for quantum communication complexity. A similar lemma was proved by Miltersen, Nisan, Safra and Wigderson for classical communication complexity, but it was not strong enough to prove a lower bound matching the upper bound of Beame and Fich. Our quantum round elimination lemma also allows us to prove rounds versus communication tradeoffs for some quantum communication complexity problems like the "greater-than" problem. We also study the "static membership" problem in the quantum cell probe model. Generalising a result of Yao, we show that if the storage scheme is implicit, that is it can only store members of the subset and `pointers', then any quantum query scheme must make $\Omega(\log n)$ probes.

Affiliated with

Also associated with

No associations

Rating

Lower bounds in the quantum cell probe model 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 Lower bounds in the quantum cell probe model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower bounds in the quantum cell probe model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-283546