IEICE TRANSACTIONS on Information
Open Access
Quantum Query Complexity of Unitary Operator Discrimination
-
Full Text Views
52
- Cite this
- Free PDF (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:={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.
- Publication
- IEICE TRANSACTIONS on Information 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
Authors
Akinori KAWACHI
Osaka University
Kenichi KAWANO
Tokushima University
Francois LE GALL
Kyoto University
Suguru TAMAKI
Kyoto University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Akinori KAWACHI, Kenichi KAWANO, Francois LE GALL, Suguru TAMAKI, "Quantum Query Complexity of Unitary Operator Discrimination" in IEICE TRANSACTIONS on Information,
vol. E102-D, no. 3, pp. 483-491, March 2019, doi: 10.1587/transinf.2018FCP0012.
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:={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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018FCP0012/_p
Copy
@ARTICLE{e102-d_3_483,
author={Akinori KAWACHI, Kenichi KAWANO, Francois LE GALL, Suguru TAMAKI, },
journal={IEICE TRANSACTIONS on Information},
title={Quantum Query Complexity of Unitary Operator Discrimination},
year={2019},
volume={E102-D},
number={3},
pages={483-491},
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:={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.},
keywords={},
doi={10.1587/transinf.2018FCP0012},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Quantum Query Complexity of Unitary Operator Discrimination
T2 - IEICE TRANSACTIONS on Information
SP - 483
EP - 491
AU - Akinori KAWACHI
AU - Kenichi KAWANO
AU - Francois LE GALL
AU - Suguru TAMAKI
PY - 2019
DO - 10.1587/transinf.2018FCP0012
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2019
AB - 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.
ER -
English
