Search Results

Documents authored by Kundu, Srijita

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.21
Oracle Separation of QMA and QCMA with Bounded Adaptivity

Authors: Shalev Ben-David and Srijita Kundu

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We give an oracle separation between QMA and QCMA for quantum algorithms that have bounded adaptivity in their oracle queries; that is, the number of rounds of oracle calls is small, though each round may involve polynomially many queries in parallel. Our oracle construction is a simplified version of the construction used recently by Li, Liu, Pelecanos, and Yamakawa (2023), who showed an oracle separation between QMA and QCMA when the quantum algorithms are only allowed to access the oracle classically. To prove our results, we introduce a property of relations called slipperiness, which may be useful for getting a fully general classical oracle separation between QMA and QCMA.
Cite as

Shalev Ben-David and Srijita Kundu. Oracle Separation of QMA and QCMA with Bounded Adaptivity. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bendavid_et_al:LIPIcs.ICALP.2024.21,
  author =	{Ben-David, Shalev and Kundu, Srijita},
  title =	{{Oracle Separation of QMA and QCMA with Bounded Adaptivity}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.21},
  URN =		{urn:nbn:de:0030-drops-201642},
  doi =		{10.4230/LIPIcs.ICALP.2024.21},
  annote =	{Keywords: Quantum computing, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.27
A Direct Product Theorem for One-Way Quantum Communication

Authors: Rahul Jain and Srijita Kundu

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation f ⊆ 𝒳×𝒴×𝒵. For any 0 < ε < δ < 1/2 and any k≥1, we show that Q¹_{1-(1-ε)^{Ω(k/log|𝒵|)}}(f^k) = Ω(k⋅Q¹_{δ}(f)), where Q¹_{ε}(f) represents the one-way entanglement-assisted quantum communication complexity of f with worst-case error ε and f^k denotes k parallel instances of f. As far as we are aware, this is the first direct product theorem for the quantum communication complexity of a general relation - direct sum theorems were previously known for one-way quantum protocols for general relations, while direct product theorems were only known for special cases. Our techniques are inspired by the parallel repetition theorems for the entangled value of two-player non-local games, under product distributions due to Jain, Pereszlényi and Yao [Rahul Jain et al., 2014], and under anchored distributions due to Bavarian, Vidick and Yuen [Bavarian et al., 2017], as well as message compression for quantum protocols due to Jain, Radhakrishnan and Sen [Rahul Jain et al., 2005]. In particular, we show that a direct product theorem holds for the distributional one-way quantum communication complexity of f under any distribution q on 𝒳×𝒴 that is anchored on one side, i.e., there exists a y^* such that q(y^*) is constant and q(x|y^*) = q(x) for all x. This allows us to show a direct product theorem for general distributions, since for any relation f and any distribution p on its inputs, we can define a modified relation f̃ which has an anchored distribution q close to p, such that a protocol that fails with probability at most ε for f̃ under q can be used to give a protocol that fails with probability at most ε + ζ for f under p. Our techniques also work for entangled non-local games which have input distributions anchored on any one side, i.e., either there exists a y^* as previously specified, or there exists an x^* such that q(x^*) is constant and q(y|x^*) = q(y) for all y. In particular, we show that for any game G = (q, 𝒳×𝒴, 𝒜×ℬ, 𝖵) where q is a distribution on 𝒳×𝒴 anchored on any one side with constant anchoring probability, then ω^*(G^k) = (1 - (1-ω^*(G))⁵) ^{Ω(k/(log(|𝒜|⋅|ℬ|)))} where ω^*(G) represents the entangled value of the game G. This is a generalization of the result of [Bavarian et al., 2017], who proved a parallel repetition theorem for games anchored on both sides, i.e., where both a special x^* and a special y^* exist, and potentially a simplification of their proof.
Cite as

Rahul Jain and Srijita Kundu. A Direct Product Theorem for One-Way Quantum Communication. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 27:1-27:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jain_et_al:LIPIcs.CCC.2021.27,
  author =	{Jain, Rahul and Kundu, Srijita},
  title =	{{A Direct Product Theorem for One-Way Quantum Communication}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{27:1--27:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.27},
  URN =		{urn:nbn:de:0030-drops-143017},
  doi =		{10.4230/LIPIcs.CCC.2021.27},
  annote =	{Keywords: Direct product theorem, parallel repetition theorem, quantum communication, one-way protocols, communication complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.30
On Query-To-Communication Lifting for Adversary Bounds

Authors: Anurag Anshu, Shalev Ben-David, and Srijita Kundu

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1) We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2) Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain "honest-but-curious" model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3) Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.
Cite as

Anurag Anshu, Shalev Ben-David, and Srijita Kundu. On Query-To-Communication Lifting for Adversary Bounds. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 30:1-30:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{anshu_et_al:LIPIcs.CCC.2021.30,
  author =	{Anshu, Anurag and Ben-David, Shalev and Kundu, Srijita},
  title =	{{On Query-To-Communication Lifting for Adversary Bounds}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{30:1--30:39},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.30},
  URN =		{urn:nbn:de:0030-drops-143042},
  doi =		{10.4230/LIPIcs.CCC.2021.30},
  annote =	{Keywords: Quantum computing, query complexity, communication complexity, lifting theorems, adversary method}
}
Document
DOI: 10.4230/LIPIcs.TQC.2020.12
A Device-Independent Protocol for XOR Oblivious Transfer

Authors: Srijita Kundu, Jamie Sikora, and Ernest Y.-Z. Tan

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract
Oblivious transfer is a cryptographic primitive where Alice has two bits and Bob wishes to learn some function of them. Ideally, Alice should not learn Bob’s desired function choice and Bob should not learn any more than logically implied by the function value. While decent quantum protocols for this task are known, many quickly become insecure if an adversary were to control the quantum devices used in the implementation of the protocol. Here we present how some existing protocols fail in this device-independent framework, and give a fully-device independent quantum protocol for XOR oblivious transfer which is provably more secure than any classical protocol.
Cite as

Srijita Kundu, Jamie Sikora, and Ernest Y.-Z. Tan. A Device-Independent Protocol for XOR Oblivious Transfer. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kundu_et_al:LIPIcs.TQC.2020.12,
  author =	{Kundu, Srijita and Sikora, Jamie and Tan, Ernest Y.-Z.},
  title =	{{A Device-Independent Protocol for XOR Oblivious Transfer}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.12},
  URN =		{urn:nbn:de:0030-drops-127579},
  doi =		{10.4230/LIPIcs.TQC.2020.12},
  annote =	{Keywords: Quantum cryptography, device independence, oblivious transfer, semidefinite programming, security analysis}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.10
A Composition Theorem for Randomized Query Complexity

Authors: Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, and Swagato Sanyal

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract
Let the randomized query complexity of a relation for error probability epsilon be denoted by R_epsilon(). We prove that for any relation f contained in {0,1}^n times R and Boolean function g:{0,1}^m -> {0,1}, R_{1/3}(f o g^n) = Omega(R_{4/9}(f).R_{1/2-1/n^4}(g)), where f o g^n is the relation obtained by composing f and g. We also show using an XOR lemma that R_{1/3}(f o (g^{xor}_{O(log n)})^n) = Omega(log n . R_{4/9}(f) . R_{1/3}(g))$, where g^{xor}_{O(log n)} is the function obtained by composing the XOR function on O(log n) bits and g.
Cite as

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, and Swagato Sanyal. A Composition Theorem for Randomized Query Complexity. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{anshu_et_al:LIPIcs.FSTTCS.2017.10,
  author =	{Anshu, Anurag and Gavinsky, Dmitry and Jain, Rahul and Kundu, Srijita and Lee, Troy and Mukhopadhyay, Priyanka and Santha, Miklos and Sanyal, Swagato},
  title =	{{A Composition Theorem for Randomized Query Complexity}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{10:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.10},
  URN =		{urn:nbn:de:0030-drops-83967},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.10},
  annote =	{Keywords: Query algorithms and complexity, Decision trees, Composition theorem, XOR lemma, Hardness amplification}
}
Document
DOI: 10.4230/LIPIcs.TQC.2014.76
Optimal Bounds for Parity-Oblivious Random Access Codes with Applications

Authors: André Chailloux, Iordanis Kerenidis, Srijita Kundu, and Jamie Sikora

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)

Abstract
Random Access Codes is an information task that has been extensively studied and found many applications in quantum information. In this scenario, Alice receives an n-bit string x, and wishes to encode x into a quantum state rho_x, such that Bob, when receiving the state rho_x, can choose any bit i in [n] and recover the input bit x_i with high probability. Here we study a variant called parity-oblivious random acres codes, where we impose the cryptographic property that Bob cannot infer any information about the parity of any subset of bits of the input, apart form the single bits x_i. We provide the optimal quantum parity-oblivious random access codes and show that they are asymptotically better than the optimal classical ones. For this, we relate such encodings to a non-local game and provide tight bounds for the success probability of the non-local game via semi-definite programming. Our results provide a large non-contextuality inequality violation and resolve the main open question in [Spekkens et al., Phys. Review Letters, 2009].
Cite as

André Chailloux, Iordanis Kerenidis, Srijita Kundu, and Jamie Sikora. Optimal Bounds for Parity-Oblivious Random Access Codes with Applications. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 76-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{chailloux_et_al:LIPIcs.TQC.2014.76,
  author =	{Chailloux, Andr\'{e} and Kerenidis, Iordanis and Kundu, Srijita and Sikora, Jamie},
  title =	{{Optimal Bounds for Parity-Oblivious Random Access Codes with Applications}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{76--87},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.76},
  URN =		{urn:nbn:de:0030-drops-48084},
  doi =		{10.4230/LIPIcs.TQC.2014.76},
  annote =	{Keywords: quantum information theory, contextuality, semidefinite programming}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact