Set membership with two classical and quantum bit probes

Shyam Dhamapurkar, Shubham Vivek Pawar, Jaikumar Radhakrishnan

We consider the following problem: Given a set S of at most n elements from a universe of size m, represent it in memory as a bit string so that membership queries of the form "Is…