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.
