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.
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.
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 diamond distance between two quantum channels determines the optimal probability of distinguishing them from a single use. We give a quantum algorithm that estimates the diamond distance between two unknown d-dimensional unitary channels to within additive error ε, using O(d/ε) queries to the unitary channels and their inverses. The query complexity is optimal, as it matches the lower bound due to Jeon and Oh (npj Quantum Inf. 2026).
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.
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{d/ε,1/ε2}), where d is the channel dimension and ε 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.
Estimating the unitarity of an unknown quantum channelEprovides 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 useO(ϵ−2)andO(d⋅ϵ−2)calls toEwith coherent and incoherent accesses, respectively, wheredis the dimension of the system thatEacts on and$\epsilon istherequiredprecision.Wefurthershowthatboththed−dependenceand\epsilon −dependenceofouralgorithmsareoptimal.Aspartofourresults,wesettlethequerycomplexityofthedistinguishingproblemfordepolarizingandunitarychannelswithincoherentaccessbygivingamatchinglowerbound\Omega (\sqrt {d}),improvingthepriorbestlowerbound\Omega (\sqrt [{3}]{d})$by (Aharonov et al., 2022) and (Chen et al., FOCS 2021).