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.

Quantum computations have so far proved to be more powerful than classical computations, but quantum computers still have not been put into practical use due to several technical issues. One of the most serious problems for realizing quantum computers is decoherence that occurs inevitably since our apparatus are surrounded with environment and open systems. In this paper, we give some surveys on a variety of effects of decoherence in quantum algorithms such as Grover's database search and quantum walks, and we show how quantum algorithms work under decoherence, how sensitive they are against decoherence, and how to implement a robust quantum circuit.

We study quantum entanglement by Schmidt decomposition for some typical quantum algorithms. In the Shor's exponentially fast algorithm the quantum entanglement holds almost maximal, which is a major factor that a classical computer is not adequate to simulate quantum efficient algorithms.

We discuss applications of quantum computation to geometric data processing. Especially, we give efficient algorithms for intersection problems and proximity problems. Our algorithms are based on Brassard et al. 's amplitude amplification method, and analogous to Buhrman et al. 's algorithm for element distinctness. Revealing these applications is useful for classifying geometric problems, and also emphasizing potential usefulness of quantum computation in geometric data processing. Thus, the results will promote research and development of quantum computers and algorithms.

There are some results indicating that a quantum computer seems to be more powerful than ordinary computers. In fact, P.W. Shor showed that a quantum computer can find discrete logarithms and factor integers in polynomial time with bounded error probability. No polynomial time algorithms to find them using ordinary computers are known. In this paper, we show that the cycles in some kinds of periodic functions, e.g., functions proposed as pseudo-random generators, can be found in polynomial time with bounded error probability on a quantum Turing machine. In general, it is known that ordinary computers take exponential time to find the cycles in periodic functions.