Projects
On the Power of Adaptivity in Testing Quantum States in Fidelity
09/2026 · Joint work with Sayantan Sen and Marco Tomamichel
We study certification, equivalence testing, and independence testing for single-copy measurements with a decision gap in fidelity. For trace distance, these problems all have the same sample complexity, and can be optimally solved by the same, non-adaptive algorithm. We generalize the ℓ₂-testing framework (Diakonikolas and Kane (FOCS 2016)) to the quantum setting and derive tailored adaptive algorithms for testing equivalence and independence, which improve the known sample complexities. We also show that adaptivity is necessary for optimal equivalence testing in fidelity, but not for certification, where we provide an optimal non-adaptive algorithm. [arXiv]
Optimal Sample Complexity Lower Bounds on Conditional Independence Testing
05/2026 · Joint work with Neelkanth Mishra, Sayantan Sen, and Marco Tomamichel
We resolve the remaining open questions in the sample complexities of both conditional independence testing and conditional mutual information testing in discrete distributions, up to logarithmic factors. To do this, we generalize the lower bound constructions by Canonne, Diakonikolas, Kane, and Stewart (STOC 2018).
[COLT 2026]
Testing (Conditional) Mutual Information
05/2025 · Joint work with Sayantan Sen and Marco Tomamichel
We prove tight bounds on the sample complexity of mutual information testing and upper bounds on the sample complexity of conditional mutual information testing, both for discrete distributions. The underlying idea is a reduction to equivalence testing in Hilbert-Schmidt distance (see Diakonikolas and Kane (FOCS 2016)) between the original distribution and simulated samples of a (conditionally) independent version of the given distribution.
[COLT 2025] [arXiv]