The Quantum Complexity of Set Membership

Research paper by Radhakrishnan, Sen, Venkatesh

Indexed on: 01 Nov '02Published on: 01 Nov '02Published in: Algorithmica


We show tradeoff results between space (defined as 2r ) and number of probes (oracle calls) in this model. Our results show that the lower bounds shown in [BMRV] for the classical model also hold (with minor differences) in the quantum bit probe model. These bounds almost match the classical upper bounds. Our lower bounds are proved using linear algebraic arguments.