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]