
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Quantum Query Complexity of Unitary Operator Discrimination
Akinori KAWACHI Kenichi KAWANO Francois LE GALL Suguru TAMAKI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E102D
No.3
pp.483491 Publication Date: 2019/03/01 Publicized: 2018/11/08 Online ISSN: 17451361
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(1.1MB)
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:={U_{1}, U_{2}} under some probability distribution over S, the goal is to decide whether U=U_{1} or U=U_{2}. 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 U_{1} and U_{2}. We also show that this upper bound is essentially tight: we prove that for every θ_{cover} > 0 there exist operators U_{1} and U_{2} 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.

open access publishing via







