Research work
I have worked in the following areas:
- Quantum information theory particularly quantum Shannon theory
with a focus towards the simultaneous smoothing problem
- Quantum cryptography with a focus on zero knowledge and information
locking
- Quantum algorithms with a focus on hidden subgroup and
related problems
- Classical and quantum communication complexity
- Classical and quantum lower bounds for data structure problems
- Lower bounds for Depth-2 arithmetic circuits
Usually, I have only listed the most complete published version and the
most complete arXiv version of the
research works. In a few cases, I have listed older versions of a
research work if there is something in that version which has not been
subsumed by a later version.
Refereed papers
High probability decoupling via approximate unitary designs and efficient
relative thermalisation
with
Aditya Nema,
IEEE Transactions on Information Theory,
2024.
Earlier version in
arXiv::2002.00247,
2020.
One-Shot Non-Catalytic Distributed Purity Distillation
with
Sayantan Chakraborty and Rahul Jain,
59th Annual Allerton Conference on Communication, Control, and Computing,
2023.
Approximate unitary designs give rise to quantum channels with
super additive classical Holevo capacity,
with
Aditya Nema,
IEEE Transactions on Information Theory,
2022.
Earlier versions in
paper 9
of the Theory of Quantum Computation, Communication and Cryptography
(TQC), 2019
and
arXiv::1902.10808,
2019.
Centralised multi link measurement compression with side information,
with
Sayantan Chakraborty and Arun Padakandla,
IEEE International Symposium on Information Theory (ISIT),
2022.
Full version in
arXiv::2203.16157,
2022.
An efficient superpositional quantum Johnson-Lindenstrauss lemma via
unitary t-designs,
Quantum Information Processing,
2021.
Earlier version in
arXiv::1807.08779,
2018.
One-shot inner bounds for sending private classical information over
a quantum MAC,
with
Sayantan Chakraborty and Aditya Nema,
IEEE Information Theory Workshop (ITW),
2021.
Full version in
arXiv::2105.06100,
2021.
A multi-sender decoupling theorem and simultaneous decoding for the
quantum MAC,
with
Sayantan Chakraborty and Aditya Nema,
IEEE International Symposium on Information Theory (ISIT),
2021.
Full version in
arXiv::2102.02187,
2021.
Novel one-shot inner bounds for unassisted fully quantum channels via rate
splitting,
with
Sayantan Chakraborty and Aditya Nema,
IEEE International Symposium on Information Theory (ISIT),
2021.
Full version in
arXiv::2102.01766,
2021.
Unions, intersections and a one-shot quantum joint typicality lemma,
Sadhana,
2021.
Earlier version in
arXiv::1806.07278,
2018.
Inner bounds via simultaneous decoding in quantum network information
theory,
Sadhana,
2021.
Earlier version in
arXiv::1806.07276,
2018.
One-shot private classical capacity of quantum wiretap channel: based
on one-shot quantum covering lemma,
with Jaikumar Radhakrishnan and Naqueeb Warsi,
7th International Conference on Quantum Cryptography (QCRYPT), 2017.
Full version at
arXiv::1703.01932.
One-shot Marton inner bound for classical-quantum broadcast channel,
with
Jaikumar Radhakrishnan and Naqueeb Warsi,
IEEE Transactions on Information Theory,
2016.
Earlier version in
arXiv::1410.3248,
2014.
Hidden translation and translating coset in quantum computing,
with
Katalin Friedl, Gabor Ivanyos, Frederic Magniez and Miklos Santha,
SIAM Journal on Computing,
2014.
Earlier versions in
pages 1-9
of ACM Symposium on Theory of Computing (STOC), 2003 and
arXiv::quant-ph/0211091,
2002.
From low-distortion norm embeddings to explicit uncertainty relations and
efficient information locking,
with
Omar Fawzi and Patrick Hayden,
Journal of the ACM,
2013.
Earlier versions in
pages 773-782
of the ACM Symposium on Theory of Computing (STOC), 2011 and
arXiv::1010.3007,
2010.
Classical communication over a quantum interference channel,
with
Omar Fawzi, Patrick Hayden, Ivan Savov and Mark Wilde,
IEEE Transactions on Information Theory,
2012.
Earlier versions in
pages 609-616
of the
Allerton Conference on Communication, Control, and Computing, 2011,
arXiv::1102.2955,
2011 and
arXiv::1102.2624,
2011.
Achieving the Han-Kobayashi inner bound for the quantum interference
channel,
IEEE International Symposium on Information Theory (ISIT),
2012.
Full version in
arXiv::1109.0802,
2011.
Limitations of quantum coset states for graph isomorphism,
with
Sean Hallgren, Cristopher Moore, Martin Rotteler and Alexander Russell,
Journal of the ACM,
2010.
Earlier versions in
pages 604-617
of the ACM Symposium on Theory of Computing (STOC), 2006 and
arXiv::quant-ph/0511148,
2005.
Random measurement bases, quantum state distinction and applications to
the hidden subgroup problem,
with
Jaikumar Radhakrishnan and Martin Rotteler,
Algorithmica,
2009.
Earlier versions in
pages 274-287
of the IEEE Conference on Computational Complexity (CCC), 2006,
arXiv::quant-ph/0512085,
2005,
pages 1399-1411
of the International Colloquium on Automata, Languages and Programming
(ICALP), 2005 and
arXiv::quant-ph/0503114,
2005.
Quantum testers for hidden group properties,
with
Katalin Friedl, Frederic Magniez and Miklos Santha,
Fundamenta Informaticae,
2009.
Earlier versions in
pages 419-428
of International Symposium on Mathematical Foundations of Computer Science
(MFCS), 2003 and
arXiv::quant-ph/0208184,
2002.
A property of quantum relative entropy with an application to privacy
in quantum communication,
with
Rahul Jain and Jaikumar Radhakrishnan,
Journal of the ACM,
2009.
Earlier versions in
pages 429-438
of the IEEE Symposium on Foundations of Computer Science (FOCS), 2002 and
arXiv::0705.2437,
2007.
The FOCS 2002 conference version has a full proof of the lower bound for
quantum communication protocols computing the pointer chasing function
without prior shared entanglement, which was omitted from the journal
version. Instead the journal version has a full proof of the privacy
tradeoffs required by an two party quantum communication protocol
computing the set membership / index function problem with arbitrary
prior shared entanglement.
Lower bounds for predecessor searching in the cell probe model,
with
Srinivasan Venkatesh,
Journal of Computer and System Sciences,
2008.
Earlier versions in
pages 73-83
of the IEEE Conference on Computational Complexity (CCC), 2003,
arXiv::cs.CC/0309033,
2003,
pages 358-369
of the International Colloquium on Automata, Languages and Programming
(ICALP), 2001 and
arXiv::quant-ph/0104100,
2001.
Making classical honest verifier zero knowledge protocols secure against
quantum attacks,
with
Sean Hallgren, Alexandra Kolla and Shengyu Zhang,
International Colloquium on Automata, Languages and Programming
(ICALP), 2008.
Prior entanglement, message compression and privacy in quantum
communication,
with
Rahul Jain and Jaikumar Radhakrishnan,
IEEE Conference on Computational Complexity (CCC), 2005.
Full version in
arXiv::0807.1267,
2008.
Invertible quantum operations and perfect encryption of quantum states,
with
Ashwin Nayak,
Quantum Information and Computation, 2007.
Earlier version in
arXiv::quant-ph/0605041,
2006.
A lower bound for the bounded round quantum communication complexity of
set disjointness,
with
Rahul Jain and Jaikumar Radhakrishnan,
IEEE Symposium on Foundations of Computer Science (FOCS), 2003.
Full version in
arXiv::quant-ph/0303138,
2003.
A direct sum theorem in communication complexity via message compression,
with
Rahul Jain and Jaikumar Radhakrishnan,
International Colloquium on Automata, Languages and Programming
(ICALP), 2003.
Full version in
arXiv::cs.CC/0304020,
2003.
The quantum complexity of set membership,
with
Jaikumar Radhakrishnan and Srinivasan Venkatesh,
Algorithmica, 2002.
Earlier versions in
pages 554-562
of the IEEE Symposium on Foundations of Computer Science (FOCS), 2000 and
arXiv::quant-ph/0007021,
2000.
The quantum communication complexity of the pointer chasing problem:
the bit version,
with
Rahul Jain and Jaikumar Radhakrishnan,
conference on the
Foundations of Software Technology and Theoretical Computer Science
(FSTTCS), 2002.
Depth-3 arithmetic circuits for S^2_n(X) and
extensions of the Graham-Pollack theorem,
with
Jaikumar Radhakrishnan and Sundar Vishwanathan,
conference on the
Foundations of Software Technology and Theoretical Computer Science
(FSTTCS), 2000.
Full version in
arXiv::cs.DM/0110031,
2001.
Manuscripts
Efficiently estimating average fidelity of a quantum logic gate using few
classical random bits,
with Aditya Nema,
arXiv::1901.07481,
2019.
Efficient quantum tensor product expanders and unitary t-designs
via the zigzag product,
arXiv::1808.10521,
2018.
A note on the power of quantum fingerprinting,
with Alexander Golynski,
arXiv::quant-ph/0510091,
2005.
Review articles
Quantum algorithm for the discrete logarithm problem,
Encyclopedia of Algorithms, 2016.
Earlier version in
pages 683-686
of Encyclopedia of Algorithms, 2008.
Doctoral dissertation
Here is my doctoral dissertation
and the talk given in its defence.