83 citations · 133 across the 17 of their papers we have counts for
22 papers
An exponential separation between entanglement-assisted and unassisted one-way quantum communication
Ryan Anselm, Srijita Kundu, Olivier Lalonde +1
A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet requi…
Flexible rigidity: Compiling generic trusted-preparation protocols into sequential device-independent protocols
Amir Arqand, Srijita Kundu, Ernest Y. -Z. Tan
We give a generic compiler for turning a wide class of device-dependent protocols with trusted state preparation into sequential device-independent protocols. In order for our comp…
Non-local games and communication complexity with noisy entanglement
Srijita Kundu, Olivier Lalonde
We study the impact of noise on the theories of quantum nonlocality and entanglement-assisted communication complexity. We consider non-local games and entanglement-assisted commun…
Quantum information advantage based on Bell inequalities
Rahul Jain, Srijita Kundu
Recently, Kretschmer et al. [KGD+25] presented an experimental demonstration of a proposed quantum information advantage protocol. We present an alternate proposal based on a relat…
Near-optimal entanglement-communication tradeoffs for remote state preparation
Srijita Kundu, Olivier Lalonde
We study the following task: Alice is given a classical description of a rank- projector on , and Alice and Bob want to prepare the quantum state on Bob'…
Non-Standard Oracles for Bounded-Error Complexity Classes
Avantika Agarwal, Srijita Kundu
In recent years, the quantum oracle model introduced by Aaronson and Kuperberg (2007) has found a lot of use in showing oracle separations between complexity classes and cryptograp…
Does there exist a quantum fingerprinting protocol without coherent measurements?
Atsuya Hasegawa, Srijita Kundu, François Le Gall +2
Buhrman, Cleve, Watrous, and de Wolf (PRL 2001) discovered the quantum fingerprinting protocol, which is the quantum SMP protocol with qubits communication for the equa…
Separations in query complexity for total search problems
Shalev Ben-David, Srijita Kundu
We study the query complexity analogue of the class TFNP of total search problems. We give a way to convert partial functions to total search problems under certain settings; we al…
Are uncloneable proof and advice states strictly necessary?
Rohit Chatterjee, Srijita Kundu, Supartha Podder
Yes, we show that they are. We initiate the study of languages that necessarily need uncloneable quantum proofs and advice. We define strictly uncloneable versions of the classes Q…
On the Power of Quantum Distributed Proofs
Atsuya Hasegawa, Srijita Kundu, Harumichi Nishimura
Quantum nondeterministic distributed computing was recently introduced as dQMA (distributed quantum Merlin-Arthur) protocols by Fraigniaud, Le Gall, Nishimura and Paz (ITCS 2021).…
Oracle separation of QMA and QCMA with bounded adaptivity
Shalev Ben-David, Srijita Kundu
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 smal…
Device-independent uncloneable encryption
Srijita Kundu, Ernest Y. -Z. Tan
Uncloneable encryption, first introduced by Broadbent and Lord (TQC 2020) is a quantum encryption scheme in which a quantum ciphertext cannot be distributed between two non-communi…
On the Hardness of the Minimum Distance Problem of Quantum Codes
Upendra Kapshikar, Srijita Kundu
We study the hardness of the problem of finding the distance of quantum error-correcting codes. The analogous problem for classical codes is known to be NP-hard, even in approximat…
A direct product theorem for quantum communication complexity with applications to device-independent cryptography
Rahul Jain, Srijita Kundu
We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity of an -player predicate . In particular we show that for…
On Query-to-Communication Lifting for Adversary Bounds
Anurag Anshu, Shalev Ben-David, Srijita Kundu
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…
Composably secure device-independent encryption with certified deletion
Srijita Kundu, Ernest Y. -Z. Tan
We study the task of encryption with certified deletion (ECD) introduced by Broadbent and Islam (2020), but in a device-independent setting: we show that it is possible to achieve…
A Direct Product Theorem for One-Way Quantum Communication
Rahul Jain, Srijita Kundu
We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal…
A device-independent protocol for XOR oblivious transfer
Srijita Kundu, Jamie Sikora, Ernest Y. -Z. Tan
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 choic…
Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions
Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu +2
The Fourier-Entropy Influence (FEI) Conjecture states that for any Boolean function , the Fourier entropy of is at most its influence up to a unive…
Quadratically Tight Relations for Randomized Query Complexity
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck +5
Let be a Boolean function. The certificate complexity is a complexity measure that is quadratically tight for the zero-error randomized que…
A Composition Theorem for Randomized Query Complexity
Anurag Anshu, Dmitry Gavinsky, Rahul Jain +5
Let the randomized query complexity of a relation for error probability be denoted by . We prove that for any relation an…
Optimal bounds for parity-oblivious random access codes
André Chailloux, Iordanis Kerenidis, Srijita Kundu +1
Random access coding is an information task that has been extensively studied and found many applications in quantum information. In this scenario, Alice receives an -bit string…