Abstract
We study the classical and quantum bitprobe versions of the static set membership problem : Given a subset, S (S β€ n) of a universe, π° (π° = m β« n), represent it as a binary string in memory so that the query "Is x in S?" (x β π°) can be answered by making at most t probes into the string. Let s_{A}(m,n,t) denote the minimum length of the bit string in any scheme that solves this static set membership problem. We show that for n β₯ 4
s_A(m,n,t = 2) =
πͺ(m^{11/(n1)}) (if n = 0 (mod 3));
πͺ(m^{11/n}) (if n = 1,2 (mod 3));
πͺ(m^{6/7}) (if n = 8,9).
These bounds are shown using a common scheme that is based on a graphtheoretic observation on orienting the edges of a graph of high girth. For all n β₯ 4, these bounds substantially improve on the previous best bounds known for this problem, some of which required elaborate constructions [Mirza Galib Anwarul Husain Baig and Deepanjan Kesh, 2020]. Our schemes are explicit. A lower bound of the form s_A(m,n,2) = Ξ©(m^{11/β{n/4}β}) was known for this problem. We show an improved lower bound of s_A(m,n,2) = Ξ©(m^{12/(n+3)}); this bound was previously known only for n = 3,5 [Mirza Galib Anwarul Husain Baig and Deepanjan Kesh, 2020; Mirza Galib Anwarul Husain Baig et al., 2019; Mirza Galib Anwarul Husain Baig and Deepanjan Kesh, 2018; Mirza Galib Anwarul Husain Baig et al., 2019; Mirza Galib Anwarul Husain Baig and Deepanjan Kesh, 2020].
We consider the quantum version of the problem, where access to the bitstring b β {0,1}^s is provided in the form of a quantum oracle that performs the transformation πͺ_b: iβ© β¦ (1)^{b_i} iβ©. Let s_Q(m,n,2) denote the minimum length of the bit string that solves the above set membership problem in the quantum model (with adaptive queries but no error). We show that for all n β€ m^{1/8}, we have s_{QA}(m,n,2) = πͺ(m^{7/8}). This upper bound makes crucial use of NashWilliamβs theorem [Diestel, 2005] for decomposing a graph into forests. This result is significant because, prior to this work, it was not known if quantum schemes yield any advantage over classical schemes. We also consider schemes that make a small number of quantum nonadaptive probes. In particular, we show that the space required in this case, s_{QN}(m,n = 2,t = 2) = O(βm) and s_{QN}(m,n = 2,t = 3) = O(m^{1/3}); in contrast, it is known that two nonadaptive classical probes yield no savings. Our quantum schemes are simple and use only the fact that the XOR of two bits of memory can be computed using just one quantum query to the oracle.
BibTeX  Entry
@InProceedings{dhamapurkar_et_al:LIPIcs.ICALP.2022.52,
author = {Dhamapurkar, Shyam S. and Pawar, Shubham Vivek and Radhakrishnan, Jaikumar},
title = {{Set Membership with Two Classical and Quantum Bit Probes}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {52:152:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16393},
URN = {urn:nbn:de:0030drops163932},
doi = {10.4230/LIPIcs.ICALP.2022.52},
annote = {Keywords: set membership problem, bit probe complexity, graphs with high girth, quantum data structure}
}
Keywords: 

set membership problem, bit probe complexity, graphs with high girth, quantum data structure 
Collection: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 
Issue Date: 

2022 
Date of publication: 

28.06.2022 