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

Leibniz international proceedings in informatics

On the Query Complexity of Perfect Gate Discrimination

Giulio Chiribella, Giacomo Mauro D’Ariano, Martin Roetteler

Published Jan 1, 2013• 0 citations
Publisher

Abstract

We investigate the problem of finding the minimum number of queries needed to perfectly identify an unknown quantum gate within a finite set of alternatives, considering both deterministic strategies. For unambiguous gate discrimination, where errors are not tolerated but inconclusive outcomes are allowed, we prove that parallel strategies are sufficient to identify the unknown gate with minimum number of queries and we use this fact to provide upper and lower bounds on the query complexity. In addition, we introduce the notion of generalized $t$-designs, which includes unitary t-designs and group representations as special cases. For gates forming a generalized $t$-design we prove that there is no difference between perfect probabilistic and perfect deterministic gate discrimination. Hence, evaluating of the query complexity of perfect discrimination is reduced to the easier problem of evaluating the query complexity of unambiguous discrimination.

DOI
10.4230/lipics.tqc.2013.178

Related papers

Unitary gate identification with multiple queries

Giulio Chiribella, Giacomo Mauro D’Ariano, Martin Roetteler

We assess the resources needed to identify a reversible quantum gate among a finite set of alternatives, including in our analysis both deterministic and probabilistic strategies. Among the probabilistic strategies we consider unambiguous gate discrimination, where errors are not tolerated but inconclusive outcomes are allowed, and we prove that parallel strategies are sufficient to unambiguously identify the unknown gate with minimum number of queries. This result is used to provide upper and lower bounds on the query complexity and on the minimum ancilla dimension. In addition, we introduce the notion of generalized t-designs, which includes unitary t-designs and group representations as special cases. For gates forming a generalized t-design we give an explicit expression for the maximum probability of correct gate identification and we prove that there is no gap between the performances of deterministic strategies an those of probabilistic strategies. Hence, evaluating of the query complexity of perfect deterministic discrimination is reduced to the easier problem of evaluating the query complexity of unambiguous discrimination. Finally, we consider discrimination strategies where the use of ancillas is forbidden, providing upper bounds on the number of additional queries needed to make up for the lack of entanglement with the ancillas.

•Jun 4, 2013•0 citations

Identification of a reversible quantum gate: assessing the resources

Giulio Chiribella, Giacomo Mauro D’Ariano, Martin Roetteler

We assess the resources needed to identify a reversible quantum gate among a finite set of alternatives, including in our analysis both deterministic and probabilistic strategies. Among the probabilistic strategies, we consider unambiguous gate discrimination—where errors are not tolerated but inconclusive outcomes are allowed—and we prove that parallel strategies are sufficient to unambiguously identify the unknown gate with minimum number of queries. This result is used to provide upper and lower bounds on the query complexity and on the minimum ancilla dimension. In addition, we introduce the notion of generalized t -designs, which includes unitary t -designs and group representations as special cases. For gates forming a generalized t -design we give an explicit expression for the maximum probability of correct gate identification and we prove that there is no gap between the performances of deterministic strategies and those of probabilistic strategies. Hence, evaluating of the query complexity of perfect deterministic discrimination is reduced to the easier problem of evaluating the query complexity of unambiguous discrimination. Finally, we consider discrimination strategies where the use of ancillas is forbidden, providing upper bounds on the number of additional queries needed to make up for the lack of entanglement with the ancillas.

arXiv:1306.0719•New Journal of Physics•Oct 17, 2013•13 citations

How many copies are needed for gate discrimination

Giulio Chiribella, Giacomo Mauro D’Ariano, Martin Roetteler

We address the problem of finding the minimum number of queries needed to perfectly identify an unknown gate within a finite set of alternatives. We provide a series of upper and lower bounds, by establishing a connection with the task of unambiguous discrimination, where one does not tolerate errors but allows for an inconclusive result. Our bounds show that the minimum number of queries needed for perfect discrimination is significantly smaller than the number required by the best known strategy based on pairwise tests.

Conference on Theory of Quantum Computation, Communication and Cryptography•Jan 1, 2013•0 citations

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

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.

arXiv:2504.12989•Quantum Science and Technology•Sep 23, 2025•2 citations
We investigate the problem of finding the minimum number of queries needed to perfectly identify an unknown quantum gate within a finite set of alternatives, considering both deterministic strategies. For unambiguous gate discrimination, where errors are not tolerated but inconclusive outcomes are allowed, we prove that parallel strategies are sufficient to identify the unknown gate with minimum number of queries and we use this fact to provide upper and lower bounds on the query complexity. In addition, we introduce the notion of generalized ttt-designs, which includes unitary t-designs and group representations as special cases. For gates forming a generalized ttt-design we prove that there is no difference between perfect probabilistic and perfect deterministic gate discrimination. Hence, evaluating of the query complexity of perfect discrimination is reduced to the easier problem of evaluating the query complexity of unambiguous discrimination.
We assess the resources needed to identify a reversible quantum gate among a finite set of alternatives, including in our analysis both deterministic and probabilistic strategies. Among the probabilistic strategies we consider unambiguous gate discrimination, where errors are not tolerated but inconclusive outcomes are allowed, and we prove that parallel strategies are sufficient to unambiguously identify the unknown gate with minimum number of queries. This result is used to provide upper and lower bounds on the query complexity and on the minimum ancilla dimension. In addition, we introduce the notion of generalized t-designs, which includes unitary t-designs and group representations as special cases. For gates forming a generalized t-design we give an explicit expression for the maximum probability of correct gate identification and we prove that there is no gap between the performances of deterministic strategies an those of probabilistic strategies. Hence, evaluating of the query complexity of perfect deterministic discrimination is reduced to the easier problem of evaluating the query complexity of unambiguous discrimination. Finally, we consider discrimination strategies where the use of ancillas is forbidden, providing upper bounds on the number of additional queries needed to make up for the lack of entanglement with the ancillas.
We assess the resources needed to identify a reversible quantum gate among a finite set of alternatives, including in our analysis both deterministic and probabilistic strategies. Among the probabilistic strategies, we consider unambiguous gate discrimination—where errors are not tolerated but inconclusive outcomes are allowed—and we prove that parallel strategies are sufficient to unambiguously identify the unknown gate with minimum number of queries. This result is used to provide upper and lower bounds on the query complexity and on the minimum ancilla dimension. In addition, we introduce the notion of generalized t -designs, which includes unitary t -designs and group representations as special cases. For gates forming a generalized t -design we give an explicit expression for the maximum probability of correct gate identification and we prove that there is no gap between the performances of deterministic strategies and those of probabilistic strategies. Hence, evaluating of the query complexity of perfect deterministic discrimination is reduced to the easier problem of evaluating the query complexity of unambiguous discrimination. Finally, we consider discrimination strategies where the use of ancillas is forbidden, providing upper bounds on the number of additional queries needed to make up for the lack of entanglement with the ancillas.
We address the problem of finding the minimum number of queries needed to perfectly identify an unknown gate within a finite set of alternatives. We provide a series of upper and lower bounds, by establishing a connection with the task of unambiguous discrimination, where one does not tolerate errors but allows for an inconclusive result. Our bounds show that the minimum number of queries needed for perfect discrimination is significantly smaller than the number required by the best known strategy based on pairwise tests.
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.
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.
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.