License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.52
URN: urn:nbn:de:0030-drops-163932
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16393/
Dhamapurkar, Shyam S. ;
Pawar, Shubham Vivek ;
Radhakrishnan, Jaikumar
Set Membership with Two Classical and Quantum Bit Probes
Abstract
We study the classical and quantum bit-probe 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^{1-1/(n-1)}) (if n = 0 (mod 3));
?(m^{1-1/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 graph-theoretic 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^{1-1/⌊{n/4}⌋}) was known for this problem. We show an improved lower bound of s_A(m,n,2) = Ω(m^{1-2/(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 bit-string 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 Nash-William’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 non-adaptive 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 non-adaptive 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:1--52:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16393},
URN = {urn:nbn:de:0030-drops-163932},
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 |
