Abstract
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 obtainin