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

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.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.10832Nov 17, 20250 citations

Query complexity of classical and quantum channel discrimination

Theshani Nuradha, Mark M. Wilde

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.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.

arXiv:2504.12989Quantum Science and TechnologySep 23, 20252 citations

Unitarity Estimation for Quantum Channels

Kean Chen, Qisheng Wang, Peixun Long +1 more

Estimating the unitarity of an unknown quantum channel $\mathcal {E}$ provides information on how much it is unitary, which is a basic and important problem in quantum device certification and benchmarking. Unitarity estimation can be performed with either coherent or incoherent access, where the former in general leads to better query complexity while the latter allows more practical implementations. In this paper, we provide a unified framework for unitarity estimation, which induces ancilla-efficient algorithms that use $O(\epsilon ^{-2})$ and $O(\sqrt {d}\cdot \epsilon ^{-2})$ calls to $\mathcal {E}$ with coherent and incoherent accesses, respectively, where $d$ is the dimension of the system that $\mathcal {E}$ acts on and$\epsilon $is the required precision. We further show that both the$ d $-dependence and$ \epsilon $-dependence of our algorithms are optimal. As part of our results, we settle the query complexity of the distinguishing problem for depolarizing and unitary channels with incoherent access by giving a matching lower bound$ \Omega (\sqrt {d}) $, improving the prior best lower bound$ \Omega (\sqrt [{3}]{d})$by (Aharonov et al., 2022) and (Chen et al., FOCS 2021).Estimating the unitarity of an unknown quantum channel$\mathcal {E}$provides information on how much it is unitary, which is a basic and important problem in quantum device certification and benchmarking. Unitarity estimation can be performed with either coherent or incoherent access, where the former in general leads to better query complexity while the latter allows more practical implementations. In this paper, we provide a unified framework for unitarity estimation, which induces ancilla-efficient algorithms that use$O(\epsilon ^{-2})$and$O(\sqrt {d}\cdot \epsilon ^{-2})$calls to$\mathcal {E}$with coherent and incoherent accesses, respectively, where$d$is the dimension of the system that$\mathcal {E}$acts on and$\epsilon $is the required precision. We further show that both the$d$-dependence and$\epsilon $-dependence of our algorithms are optimal. As part of our results, we settle the query complexity of the distinguishing problem for depolarizing and unitary channels with incoherent access by giving a matching lower bound$\Omega (\sqrt {d})$, improving the prior best lower bound$\Omega (\sqrt [{3}]{d})$by (Aharonov et al., 2022) and (Chen et al., FOCS 2021).

arXiv:2212.09319IEEE Transactions on Information TheoryMar 31, 202312 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.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 PhysicsApr 11, 20251 citation

Limits on Parameter Estimation of Quantum Channels

Vishal Katariya

The aim of this thesis is to develop a theoretical framework to study parameter estimation of quantum channels. We begin by describing the classical task of parameter estimation that we build upon. In its most basic form, parameter estimation is the task of obtaining an estimate of an unknown parameter from some experimental data. This experimental data can be seen as a number of samples of a parameterized probability distribution. In general, the goal of such a task is to obtain an estimate of the unknown parameter while minimizing its error. We study the task of estimating unknown parameters which are encoded in a quantum channel. A quantum channel is a map that describes the evolution of the state of a quantum system. We study this task in the sequential setting. This means that the channel in question is used multiple times, and each channel use happens subsequent to the previous one. A sequential strategy is the most general way to use, or process, a channel multiple times. Our goal is to establish lower bounds on the estimation error in such a task. These bounds are called Cramer--Rao bounds. Quantum channels encompass all possible dynamics allowed by quantum mechanics, and sequential estimation strategies capture the most general way to process multiple uses of a channel. Therefore, the bounds we develop are universally applicable. We consider the use of catalysts to enhance the power of a channel estimation strategy. This is termed amortization. The reason we do so is to investigate if an n-round sequential estimation strategy does better than a simpler parallel strategy. Quantitatively, the power of a channel for a particular estimation task is determined by the channel's Fisher information. Thus, we study how much a catalyst quantum state can enhance the Fisher information of a quantum channel by defining the amortized Fisher information. In the quantum setting, there are many Fisher information quantities that can be defined. We limit our study to two particular ones: the symmetric logarithmic derivative (SLD) Fisher information and the right logarithmic derivative (RLD) Fisher information. We establish our Cramer--Rao bounds by proving that for certain Fisher information quantities, catalyst states do not improve the performance of a sequential estimation protocol. The technical term for this is an amortization collapse. We show how such a collapse leads directly to a corresponding Cramer--Rao bound. We establish bounds both when estimating a single parameter and whenThe aim of this thesis is to develop a theoretical framework to study parameter estimation of quantum channels. We begin by describing the classical task of parameter estimation that we build upon. In its most basic form, parameter estimation is the task of obtaining an estimate of an unknown parameter from some experimental data. This experimental data can be seen as a number of samples of a parameterized probability distribution. In general, the goal of such a task is to obtain an estimate of the unknown parameter while minimizing its error. We study the task of estimating unknown parameters which are encoded in a quantum channel. A quantum channel is a map that describes the evolution of the state of a quantum system. We study this task in the sequential setting. This means that the channel in question is used multiple times, and each channel use happens subsequent to the previous one. A sequential strategy is the most general way to use, or process, a channel multiple times. Our goal is to establish lower bounds on the estimation error in such a task. These bounds are called Cramer--Rao bounds. Quantum channels encompass all possible dynamics allowed by quantum mechanics, and sequential estimation strategies capture the most general way to process multiple uses of a channel. Therefore, the bounds we develop are universally applicable. We consider the use of catalysts to enhance the power of a channel estimation strategy. This is termed amortization. The reason we do so is to investigate if an n-round sequential estimation strategy does better than a simpler parallel strategy. Quantitatively, the power of a channel for a particular estimation task is determined by the channel's Fisher information. Thus, we study how much a catalyst quantum state can enhance the Fisher information of a quantum channel by defining the amortized Fisher information. In the quantum setting, there are many Fisher information quantities that can be defined. We limit our study to two particular ones: the symmetric logarithmic derivative (SLD) Fisher information and the right logarithmic derivative (RLD) Fisher information. We establish our Cramer--Rao bounds by proving that for certain Fisher information quantities, catalyst states do not improve the performance of a sequential estimation protocol. The technical term for this is an amortization collapse. We show how such a collapse leads directly to a corresponding Cramer--Rao bound. We establish bounds both when estimating a single parameter and when

arXiv:2201.01738Civil War Book ReviewDec 15, 20210 citations

Optimal Distributed Similarity Estimation of Quantum Channels

Congcong Zheng, Kun Wang, Xutao Yu +2 more

As quantum processors are deployed across different hardware platforms and remote cloud laboratories, a basic physical question is whether two black-box devices realize the same quantum process, without relying on a trusted classical description. We formulate the core primitive for this comparison task as \emph{distributed similarity estimation of quantum channels} (DSEC): given local access to two unknown channels, estimate the normalized inner product of their Choi states. We prove that the optimal query complexity of DSEC is $Θ(\max\{\sqrt{d}/\varepsilon,1/\varepsilon^2\})$ , where $d$ is the channel dimension and $\varepsilon$ is the additive error. This matching query complexity is nontrivial: channel learning permits input choices and interleaving known operations, which makes channel learning strictly harder than state learning. We first prove an information-theoretic lower bound with this scaling, which holds even in the \emph{strongest setting}, allowing adaptive strategies, multiple rounds of classical communication, and coherent access with arbitrary ancillas. We then give a matching upper bound in the \emph{weakest setting}, namely non-adaptive and ancilla-free incoherent access, via a randomized measurement algorithm achieving this bound. Finally, we show that our algorithm achieves a quadratic improvement over classical shadow baselines. Our results provide theoretically optimal and practical algorithms for quantum device benchmarking and distributed quantum learning.As quantum processors are deployed across different hardware platforms and remote cloud laboratories, a basic physical question is whether two black-box devices realize the same quantum process, without relying on a trusted classical description. We formulate the core primitive for this comparison task as \emph{distributed similarity estimation of quantum channels} (DSEC): given local access to two unknown channels, estimate the normalized inner product of their Choi states. We prove that the optimal query complexity of DSEC is $Θ(\max\{\sqrt{d}/\varepsilon,1/\varepsilon^2\})$, where $d$ is the channel dimension and $\varepsilon$ is the additive error. This matching query complexity is nontrivial: channel learning permits input choices and interleaving known operations, which makes channel learning strictly harder than state learning. We first prove an information-theoretic lower bound with this scaling, which holds even in the \emph{strongest setting}, allowing adaptive strategies, multiple rounds of classical communication, and coherent access with arbitrary ancillas. We then give a matching upper bound in the \emph{weakest setting}, namely non-adaptive and ancilla-free incoherent access, via a randomized measurement algorithm achieving this bound. Finally, we show that our algorithm achieves a quadratic improvement over classical shadow baselines. Our results provide theoretically optimal and practical algorithms for quantum device benchmarking and distributed quantum learning.

quant-pharXiv:2512.10465Dec 12, 20250 citations

Estimating the unitarity of an unknown quantum channel

\mathcal {E}

provides information on how much it is unitary, which is a basic and important problem in quantum device certification and benchmarking. Unitarity estimation can be performed with either coherent or incoherent access, where the former in general leads to better query complexity while the latter allows more practical implementations. In this paper, we provide a unified framework for unitarity estimation, which induces ancilla-efficient algorithms that use

O(\epsilon ^{-2})

and

O(\sqrt {d}\cdot \epsilon ^{-2})

calls to

\mathcal {E}

with coherent and incoherent accesses, respectively, where

d

is the dimension of the system that

\mathcal {E}

acts on and$\epsilon

is the required precision. We further show that both the

-dependence and

\epsilon

-dependence of our algorithms are optimal. As part of our results, we settle the query complexity of the distinguishing problem for depolarizing and unitary channels with incoherent access by giving a matching lower bound

\Omega (\sqrt {d})

, improving the prior best lower bound

\Omega (\sqrt [{3}]{d})$by (Aharonov et al., 2022) and (Chen et al., FOCS 2021).

Θ(\max\{\sqrt{d}/\varepsilon,1/\varepsilon^2\})

, where

d

is the channel dimension and

\varepsilon

is the additive error. This matching query complexity is nontrivial: channel learning permits input choices and interleaving known operations, which makes channel learning strictly harder than state learning. We first prove an information-theoretic lower bound with this scaling, which holds even in the \emph{strongest setting}, allowing adaptive strategies, multiple rounds of classical communication, and coherent access with arbitrary ancillas. We then give a matching upper bound in the \emph{weakest setting}, namely non-adaptive and ancilla-free incoherent access, via a randomized measurement algorithm achieving this bound. Finally, we show that our algorithm achieves a quadratic improvement over classical shadow baselines. Our results provide theoretically optimal and practical algorithms for quantum device benchmarking and distributed quantum learning.