Quantum Query Complexity of Unitary Operator Discrimination

Akinori KAWACHI  Kenichi KAWANO  Francois LE GALL  Suguru TAMAKI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.3   pp.483-491
Publication Date: 2019/03/01
Publicized: 2018/11/08
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018FCP0012
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
Category: 
Keyword: 
quantum algorithms,  quantum information theory,  query complexity,  

Full Text: FreePDF

Summary: 
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} heta_{ m cover}^{-1}} ceil$ 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{ rac{2}{3 heta_{ m cover}}} ceil$ queries under uniform distribution over S.