1 Search Results for "Dhamapurkar, Shyam S."


Document
Track A: Algorithms, Complexity and Games
Set Membership with Two Classical and Quantum Bit Probes

Authors: Shyam S. Dhamapurkar, Shubham Vivek Pawar, and Jaikumar Radhakrishnan

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


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.

Cite as

Shyam S. Dhamapurkar, Shubham Vivek Pawar, and Jaikumar Radhakrishnan. Set Membership with Two Classical and Quantum Bit Probes. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 52:1-52:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.52},
  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}
}
  • Refine by Author
  • 1 Dhamapurkar, Shyam S.
  • 1 Pawar, Shubham Vivek
  • 1 Radhakrishnan, Jaikumar

  • Refine by Classification
  • 1 Theory of computation
  • 1 Theory of computation → Computational complexity and cryptography

  • Refine by Keyword
  • 1 bit probe complexity
  • 1 graphs with high girth
  • 1 quantum data structure
  • 1 set membership problem

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail