Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2504.12989 · Quantum Science and Technology

Query complexity of classical and quantum channel discrimination

Theshani Nuradha, Mark M. Wilde

Published Sep 23, 2025• 9 citations
arXivHTMLPDF

Abstract

Abstract 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 special cases 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 when the error probability does not exceed a fixed threshold, we provide a more precise characterization of query complexity under a similar error probability threshold constraint. 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ényi and Petz–Rényi 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.

DOI
10.1088/2058-9565/ae0a79

Related papers

Query complexities of quantum channel discrimination and estimation: A unified approach

Zixin Huang, Johannes Jakob Meyer, Theshani Nuradha +1 more

The goal of quantum channel discrimination and estimation is to determine the identity of an unknown channel from a discrete or continuous set, respectively. The query complexity of these tasks is equal to the minimum number of times one must call an unknown channel to identify it within a desired threshold on the error probability. In this paper, we establish lower bounds on the query complexities of channel discrimination and estimation, in both the parallel and adaptive access models. We do so by establishing new or applying known upper bounds on the squared Bures distance and symmetric logarithmic derivative Fisher information of channels. Phrasing our statements and proofs in terms of isometric extensions of quantum channels allows us to give conceptually simple proofs for both novel and known bounds. We also provide alternative proofs for several established results in an effort to present a consistent and unified framework for quantum channel discrimination and estimation, which we believe will be helpful in addressing future questions in the field.

quant-pharXiv:2511.10832•Nov 17, 2025•4 citations

Sampling complexity of quantum channel discrimination

Lei S. Li, Zhe Ji, Qing-Wen Wang +2 more

Abstract In this paper, we study the problem of sampling complexity for channel discrimination with respect to two different strategies: product strategy and adaptive strategy. We first formally introduce the definitions of the sampling complexity of the channels under the framework of hypothesis testing , wherein the goal is to determine the minimum number of samples needed to reach a desired error probability. We then establish the lower and upper bounds on the sampling complexity of the symmetric, asymmetric, and error exponent hypothesis testing settings. We show that, by imposing product strategy on testing, the bounds are always characterized by the generalized channel divergence, while with adaptive strategy, the bounds are characterized by the amortized channel divergence. Finally, we analyze two concrete examples, and obtain that the adaptive strategy can not lead to an advantage to the problem of determining the sampling complexity for classical-quantum channels, which can bring advantages for generalized amplitude damping channels.

Communications in Theoretical Physics•Apr 11, 2025•4 citations

Query complexities of quantum channel discrimination and estimation: A unified approach

Mark M. Wilde

The goal of quantum channel discrimination and estimation is to determine the identity of an unknown channel from a discrete or continuous set, respectively. The query complexity of these tasks is equal to the minimum number of times one must call an unknown channel to identify it within a desired threshold on the error probability. In this paper, we establish lower bounds on the query complexities of channel discrimination and estimation, in both the parallel and adaptive access models. We do so by establishing new or applying known upper bounds on the squared Bures distance and symmetric logarithmic derivative Fisher information of channels. Phrasing our statements and proofs in terms of isometric extensions of quantum channels allows us to give conceptually simple proofs for both novel and known bounds. We also provide alternative proofs for several established results in an effort to present a consistent and unified framework for quantum channel discrimination and estimation, which we believe will be helpful in addressing future questions in the field. Joint work with Zixin Huang, Johannes Jakob Meyer, and Theshani Nuradha.

•Feb 20, 2026•0 citations

Some bounds on the minimum number of queries required for quantum channel perfect discrimination

Cheng Zhu Lu, Jianxin Chen, Runyao Duan

We prove a lower bound on the $q$-maximal fidelities between two quantum channels $\E_0$ and $\E_1$ and an upper bound on the $q$-maximal fidelities between a quantum channel $\E$ and an identity $\I$. Then we apply these two bounds to provide a simple sufficient and necessary condition for sequential perfect distinguishability between $\E$ and $\I$ and provide both a lower bound and an upper bound on the minimum number of queries required to sequentially perfectly discriminating $\E$ and $\I$. Interestingly, in the $2$-dimensional case, both bounds coincide. Based on the optimal perfect discrimination protocol presented in \cite{DFY09}, we can further generalize the lower bound and upper bound to the minimum number of queries to perfectly discriminating $\E$ and $I$ over all possible discrimination schemes. Finally the two lower bounds are shown remain working for perfectly discriminating general two quantum channels $\E_0$ and $\E_1$ in sequential scheme and over all possible discrimination schemes respectively.

Quantum Information and Computation•Jan 1, 2012•3 citations

An invitation to the sample complexity of quantum hypothesis testing

Hao–Chung Cheng, Nilanjana Datta, Nana Liu +3 more

We study the sample complexity of quantum hypothesis testing, wherein the goal is to determine the minimum number of samples needed to reach a desired error probability. We characterize the sample complexity of binary quantum hypothesis testing in the symmetric and asymmetric settings, and we provide bounds on the sample complexity of multiple quantum hypothesis testing. The final part of our paper outlines and reviews how sample complexity of quantum hypothesis testing is relevant to a broad swathe of research areas and can enhance understanding of many fundamental concepts, including quantum algorithms for simulation and search, quantum learning and classification, and foundations of quantum mechanics. As such, we view our paper as an invitation to researchers coming from different communities to study and contribute to the problem of sample complexity of quantum hypothesis testing, and we outline a number of open directions for future research.

arXiv:2403.17868•npj Quantum Information•Jun 5, 2025•24 citations

Multiple quantum hypothesis testing expressions and classical-quantum channel converse bounds

Gonzalo Vazquez-Vilar

Alternative exact expressions are derived for the minimum error probability of a hypothesis test discriminating among M quantum states. The first expression corresponds to the error probability of a binary hypothesis test with certain parameters; the second involves the optimization of a given information-spectrum measure. Particularized in the classical-quantum channel coding setting, this characterization implies the tightness of two existing converse bounds; one derived by Matthews and Wehner using hypothesis-testing, and one obtained by Hayashi and Nagaoka via an information-spectrum approach.

arXiv:1607.07625•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•7 citations
Abstract 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 special cases 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 when the error probability does not exceed a fixed threshold, we provide a more precise characterization of query complexity under a similar error probability threshold constraint. 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ényi and Petz–Rényi 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.
The goal of quantum channel discrimination and estimation is to determine the identity of an unknown channel from a discrete or continuous set, respectively. The query complexity of these tasks is equal to the minimum number of times one must call an unknown channel to identify it within a desired threshold on the error probability. In this paper, we establish lower bounds on the query complexities of channel discrimination and estimation, in both the parallel and adaptive access models. We do so by establishing new or applying known upper bounds on the squared Bures distance and symmetric logarithmic derivative Fisher information of channels. Phrasing our statements and proofs in terms of isometric extensions of quantum channels allows us to give conceptually simple proofs for both novel and known bounds. We also provide alternative proofs for several established results in an effort to present a consistent and unified framework for quantum channel discrimination and estimation, which we believe will be helpful in addressing future questions in the field.
Abstract In this paper, we study the problem of sampling complexity for channel discrimination with respect to two different strategies: product strategy and adaptive strategy. We first formally introduce the definitions of the sampling complexity of the channels under the framework of hypothesis testing , wherein the goal is to determine the minimum number of samples needed to reach a desired error probability. We then establish the lower and upper bounds on the sampling complexity of the symmetric, asymmetric, and error exponent hypothesis testing settings. We show that, by imposing product strategy on testing, the bounds are always characterized by the generalized channel divergence, while with adaptive strategy, the bounds are characterized by the amortized channel divergence. Finally, we analyze two concrete examples, and obtain that the adaptive strategy can not lead to an advantage to the problem of determining the sampling complexity for classical-quantum channels, which can bring advantages for generalized amplitude damping channels.
The goal of quantum channel discrimination and estimation is to determine the identity of an unknown channel from a discrete or continuous set, respectively. The query complexity of these tasks is equal to the minimum number of times one must call an unknown channel to identify it within a desired threshold on the error probability. In this paper, we establish lower bounds on the query complexities of channel discrimination and estimation, in both the parallel and adaptive access models. We do so by establishing new or applying known upper bounds on the squared Bures distance and symmetric logarithmic derivative Fisher information of channels. Phrasing our statements and proofs in terms of isometric extensions of quantum channels allows us to give conceptually simple proofs for both novel and known bounds. We also provide alternative proofs for several established results in an effort to present a consistent and unified framework for quantum channel discrimination and estimation, which we believe will be helpful in addressing future questions in the field. Joint work with Zixin Huang, Johannes Jakob Meyer, and Theshani Nuradha.
We prove a lower bound on the qqq-maximal fidelities between two quantum channels $\E_0$ and $\E_1$ and an upper bound on the qqq-maximal fidelities between a quantum channel $\E$ and an identity $\I$. Then we apply these two bounds to provide a simple sufficient and necessary condition for sequential perfect distinguishability between $\E$ and $\I$ and provide both a lower bound and an upper bound on the minimum number of queries required to sequentially perfectly discriminating $\E$ and $\I$. Interestingly, in the 222-dimensional case, both bounds coincide. Based on the optimal perfect discrimination protocol presented in \cite{DFY09}, we can further generalize the lower bound and upper bound to the minimum number of queries to perfectly discriminating $\E$ and III over all possible discrimination schemes. Finally the two lower bounds are shown remain working for perfectly discriminating general two quantum channels $\E_0$ and $\E_1$ in sequential scheme and over all possible discrimination schemes respectively.
We study the sample complexity of quantum hypothesis testing, wherein the goal is to determine the minimum number of samples needed to reach a desired error probability. We characterize the sample complexity of binary quantum hypothesis testing in the symmetric and asymmetric settings, and we provide bounds on the sample complexity of multiple quantum hypothesis testing. The final part of our paper outlines and reviews how sample complexity of quantum hypothesis testing is relevant to a broad swathe of research areas and can enhance understanding of many fundamental concepts, including quantum algorithms for simulation and search, quantum learning and classification, and foundations of quantum mechanics. As such, we view our paper as an invitation to researchers coming from different communities to study and contribute to the problem of sample complexity of quantum hypothesis testing, and we outline a number of open directions for future research.
Alternative exact expressions are derived for the minimum error probability of a hypothesis test discriminating among M quantum states. The first expression corresponds to the error probability of a binary hypothesis test with certain parameters; the second involves the optimization of a given information-spectrum measure. Particularized in the classical-quantum channel coding setting, this characterization implies the tightness of two existing converse bounds; one derived by Matthews and Wehner using hypothesis-testing, and one obtained by Hayashi and Nagaoka via an information-spectrum approach.