# Query Complexity of Classical and Quantum Channel Discrimination

arXiv: https://arxiv.org/abs/2504.12989 · HTML: https://mlsanity.com/paper/2504.12989/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 66 references that are in the map.
- First posted on arXiv 17 Apr 2025.

## Builds on (most cited first, 6 of 6)

- [Quantum Differential Privacy: An Information Theory Perspective](https://mlsanity.com/paper/2202.10717/) (2022)
- [Quantum Pufferfish Privacy: A Flexible Privacy Framework for Quantum Systems](https://mlsanity.com/paper/2306.13054/) (2023)
- [The Sample Complexity of Simple Binary Hypothesis Testing](https://mlsanity.com/paper/2403.16981/) (2024)
- [Contraction of Private Quantum Channels and Private Quantum Hypothesis Testing](https://mlsanity.com/paper/2406.18651/) (2024)
- [An invitation to the sample complexity of quantum hypothesis testing](https://mlsanity.com/paper/2403.17868/) (2024)
- [Quantum Doeblin Coefficients: Interpretations and Applications](https://mlsanity.com/paper/2503.22823/) (2025)

## Built on by (most cited first, 1 of 1)

- [Privacy-Utility Tradeoffs in Quantum Information Processing](https://mlsanity.com/paper/2602.10510/) (2026)

## Abstract (arXiv)

Quantum channel discrimination has been studied from an information-theoretic perspective, wherein one is interested in the optimal decay rate of error probabilities as a function of the number of unknown channel accesses. In this paper, we study the query complexity of quantum channel discrimination, wherein the goal is to determine the minimum number of channel uses needed to reach a desired error probability. To this end, we show that the query complexity of binary channel discrimination depends logarithmically on the inverse error probability and inversely on the negative logarithm of the (geometric and Holevo) channel fidelity. As a special case of these findings, we precisely characterize the query complexity of discriminating two classical channels and two classical-quantum channels. Furthermore, by obtaining an optimal characterization of the sample complexity of quantum hypothesis testing, including prior probabilities, we provide a more precise characterization of query complexity when the error probability does not exceed a fixed threshold. We also provide lower and upper bounds on the query complexity of binary asymmetric channel discrimination and multiple quantum channel discrimination. For the former, the query complexity depends on the geometric R'enyi and Petz R'enyi channel divergences, while for the latter, it depends on the negative logarithm of the (geometric and Uhlmann) channel fidelity. For multiple channel discrimination, the upper bound scales as the logarithm of the number of channels.