Unitary operator discrimination is a fundamental problem in quantum information theory. The basic version of this problem can be described as follows: Given a black box implementing a unitary operator U∈S:={U1, U2} under some probability distribution over S, the goal is to decide whether U=U1 or U=U2. In this paper, we consider the query complexity of this problem. We show that there exists a quantum algorithm that solves this problem with bounded error probability using $\lceil{\sqrt{6}\theta_{\rm cover}^{-1}}\rceil$ queries to the black box in the worst case, i.e., under any probability distribution over S, where the parameter θcover, which is determined by the eigenvalues of $U_1^\dagger {U_2}$ , represents the “closeness” between U1 and U2. We also show that this upper bound is essentially tight: we prove that for every θcover > 0 there exist operators U1 and U2 such that any quantum algorithm solving this problem with bounded error probability requires at least $\lceil{\frac{2}{3 \theta_{\rm cover}}}\rceil$ queries under uniform distribution over S.Unitary operator discrimination is a fundamental problem in quantum information theory. The basic version of this problem can be described as follows: Given a black box implementing a unitary operator U∈S:={U1, U2} under some probability distribution over S, the goal is to decide whether U=U1 or U=U2. In this paper, we consider the query complexity of this problem. We show that there exists a quantum algorithm that solves this problem with bounded error probability using $\lceil{\sqrt{6}\theta_{\rm cover}^{-1}}\rceil$ queries to the black box in the worst case, i.e., under any probability distribution over S, where the parameter θcover, which is determined by the eigenvalues of $U_1^\dagger {U_2}$, represents the “closeness” between U1 and U2. We also show that this upper bound is essentially tight: we prove that for every θcover > 0 there exist operators U1 and U2 such that any quantum algorithm solving this problem with bounded error probability requires at least $\lceil{\frac{2}{3 \theta_{\rm cover}}}\rceil$ queries under uniform distribution over S.

IEICE Transactions on Information and SystemsFeb 28, 20193 citations

Parameterized query complexity in quantum computation

Parijat Prashun Purohit

Jan 1, 20170 citations

On the Query Complexity of Perfect Gate Discrimination

Giulio Chiribella, Giacomo Mauro D’Ariano, Martin Roetteler

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

Leibniz international proceedings in informaticsJan 1, 20130 citations

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.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, 20130 citations

\lceil{\sqrt{6}\theta_{\rm cover}^{-1}}\rceil

queries to the black box in the worst case, i.e., under any probability distribution over S, where the parameter θcover, which is determined by the eigenvalues of

U_1^\dagger {U_2}

, represents the “closeness” between U1 and U2. We also show that this upper bound is essentially tight: we prove that for every θcover > 0 there exist operators U1 and U2 such that any quantum algorithm solving this problem with bounded error probability requires at least

\lceil{\frac{2}{3 \theta_{\rm cover}}}\rceil

queries under uniform distribution over S.

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.