论文标题
统一操作歧视的查询复杂性
Query complexity of unitary operation discrimination
论文作者
论文摘要
统一操作的歧视在量子计算和信息中至关重要。许多量子算法，包括众所周知的Deutsch-Jozsa算法，Simon的算法和Grover的算法基本上可以被视为在个人或一组单一操作（Oracle Operators）之间有区别。区分两个统一操作$ u $和$ v $的问题可以描述为：给定$ x \ in \ {u，v \} $，确定哪个$ x $是。如果$ x $具有多个副本，则可以设计一个自适应过程，该过程将多个查询带到$ x $，以输出$ x $的标识结果。在本文中，我们考虑了问题：在$ u $和$ v $之间实现所需的故障概率$ε$需要多少查询。我们在一个统一的框架中证明：（i）如果$ u $和$ v $被限制了限制错误$ε$，那么查询$ t $的数量必须满足$ t \ geq \ left \ left \ lew \ lceil \ frac {2 \ sqrt {2 \ sqrt {1-4ε（1-ε（1-ε）}}} $^use（use use unife）它们被单方面错误$ε$;然后有$ t \ geq \ weft \ lceil \ frac {2 \ sqrt {1- sqrt {1-ε^2}} {θ（u^\ dagger v）} \ right \ right \ right \ rceil $，wher表示最小的弧的长度，其中包含单位圆上$ w $的所有特征值。
Discrimination of unitary operations is fundamental in quantum computation and information. A lot of quantum algorithms including the well-known Deutsch-Jozsa algorithm, Simon's algorithm, and Grover's algorithm can essentially be regarded as discriminating among individual, or sets of unitary operations (oracle operators). The problem of discriminating between two unitary operations $U$ and $V$ can be described as: Given $X\in\{U, V\}$, determine which one $X$ is. If $X$ is given with multiple copies, then one can design an adaptive procedure that takes multiple queries to $X$ to output the identification result of $X$. In this paper, we consider the problem: How many queries are required for achieving a desired failure probability $ε$ of discrimination between $U$ and $V$. We prove in a uniform framework: (i) if $U$ and $V$ are discriminated with bound error $ε$ , then the number of queries $T$ must satisfy $T\geq \left\lceil\frac{2\sqrt{1-4ε(1-ε)}}{Θ(U^\dagger V)}\right\rceil$, and (ii) if they are discriminated with one-sided error $ε$, then there is $T\geq \left\lceil\frac{2\sqrt{1-ε^2}}{Θ(U^\dagger V)}\right\rceil$, where $\lceil k\rceil$ denotes the minimum integer not less than $k$ and $Θ(W)$ denotes the length of the smallest arc containing all the eigenvalues of $W$ on the unit circle.
