Lower bounds for testing the completely depolarizing channel
We study lower bounds to the query complexity of testing whether an unknown quantum channel mapping a $d_{\mathrm{in}}$-dimensional input to a $d_{\mathrm{out}}$-dimensional output is the completely depolarizing channel or is $\varepsilon$-far from it in diamond distance. We show that for this task (i) any ancilla-assisted, coherent, adaptive tester requires at least $Ω(d_{\mathrm{in}}d_{\mathrm{out}}/\varepsilon^2)$ queries; (ii) any ancilla-assisted, coherent, non-adaptive tester requires at least $\max\{Ω(d_{\mathrm{in}}^{1.5}d_{\mathrm{out}}/\varepsilon^2), Ω(d_{\mathrm{in}}^{2}/\varepsilon^2)\}$ queries. We also show that these lower bounds apply to the more general problem of determining whether an unknown channel belongs to the set of all state-replacement channels or is $\varepsilon$-far from the entire set in diamond distance.
Authors
- Andrew Jackson (ORCID: https://orcid.org/0000-0002-5981-1604)
- Animesh Datta (ORCID: https://orcid.org/0000-0003-4021-4655)
- Hirak Ghosh (ORCID: https://orcid.org/0000-0002-3692-2387)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-16
- DOI
- https://doi.org/10.48550/arxiv.2611.20366
- Primary Topic
- Quantum Computing Algorithms and Architecture
- Type
- preprint