Quantum bitprobe

Abstract

We use the quantum bit probe model to study the static membership problem (data structure problem). The data structure is stored classically by the probing scheme is quantum. Like most problem the goal is to reduce the resources used. The resources used here are space and number of probes (to the data structure). We study the space complexity by keep the number of probes to two. Our results - 1. We give a exact non-adaptive scheme that has sample complexity O(m1/2 ) which show the lower bound got by the polynomial method in (1) is tight. 2. We show a way to construct quantum scheme that handle subsets of size 2k + 1, is the same as drawing bipartite graphs of girth > 2k . 3. We show that sample complexity for the quantum scheme is less than the classical scheme which was shown to be m in (2). That is we give an upper bound for quantum schemes. 4. We borrow ideas we used to construct the quantum schemes to construct a adaptive classical scheme to handle subsets of size at most 4, whose sample complexity is O(m3/4 ). This results is better than the currently best know result of O(m5/6 ), a result in (3).This shows that ”quantum way” of ”looking” at a problem at time gives better insights to classical problems.