Query Complexity of quantum biased oracles with explicit bias rate

Tomoya Suzuki (0451068)


In quantum computing, query complexity is often used as a measure of the performance of algorithms.

We investigate the query complexity of quantum biased oracles. Suppose that the biased oracles answer queries correctly with probability at least 1/2+e. Given such an oracle, we present an algorithm to simulate a single query to an oracle which answers queries correctly with probability at least 2/3, using O(1/e) queries to the given oracle. For searching problems, combining the algorithm with a known result, we can obtain an optimal algorithm. The simulating algorithm works effectively when we know the value of e. We also consider the situation that no knowledge about e are given. Moreover, we present a method to derive lower bounds for quantum biased oracles in more general form than the known method.

The results relative to the known results and the simulating algorithm will be presented.