Quantum Query Complexity of Unitary Operator Discrimination

• KAWACHI Akinori

  Osaka University

• KAWANO Kenichi

  Tokushima University

• LE GALL François

  Kyoto University

• TAMAKI Suguru

  Kyoto University

Abstract

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₁, U₂} under some probability distribution over S, the goal is to decide whether U=U₁ or U=U₂. 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 U₁ and U₂. We also show that this upper bound is essentially tight: we prove that for every θ_cover > 0 there exist operators U₁ and U₂ 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.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E102.D (3), 483-491, 2019-03-01

  The Institute of Electronics, Information and Communication Engineers

Keywords

• quantum algorithms
• quantum information theory
• query complexity

Details

• CRID: 1390845713054607616
• NII Article ID: 130007606941
• DOI: 10.1587/transinf.2018fcp0012
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E102.D/3/E102.D_2018FCP0012/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed