Query complexity of unitary operation discrimination

Discrimination of unitary operations is fundamental in quantum computation and information. A lot of quantum algorithms including the well-known Deutsch-Jozsa algorithm, Simon algorithm, and Grover 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 $Xin{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 $epsilon$ of discrimination between $U$ and $V$. We prove in a uniform framework: (i) if $U$ and $V$ are discriminated with bound error $epsilon$ , then the number of queries $T$ must satisfy $Tgeq leftlceilfrac{2sqrt{1-4epsilon(1-epsilon)}}{Theta (U^dagger V)}rightrceil$, and (ii) if they are discriminated with one-sided error $epsilon$, then there is $Tgeq leftlceilfrac{2sqrt{1-epsilon}}{Theta (U^dagger V)}rightrceil$, where $Theta(W)$ denotes the length of the smallest arc containing all the eigenvalues of $W$ on the unit circle.