Noise-Tolerant Quantum Oracles (New Aspects of Theoretical Computer Science)

Julia Kempe, Elwyn R. Berlekamp, K. Birgitta Whaley

Kazuo Iwama, Akinori Kawachi, Rudy Raymond +1 more

The oracle identification problem (OIP) was introduced by Ambainis et.al. [4], which is given as a set $S$ of $M$ oracles and a hidden oracle $f$ .Our task is to figure out which oracle in $S$ is equal to the hidden $f$ by doing queries to $f$ .OIP includes several problems such as Grover Search as special cases.In this paper, we design robust algorithms, i.e., those which are tolerant against noisy oracles, for OIP.Our results include: (i) For any oracle set $S$ such that $|S|$ is polynomial in $N$ , $O(\sqrt{N})$ queries are enough to identify the hidden oracle, which is obviously optimal since this OIP includes Grover Search as a special case, (ii) For the case that $|S|\leq 2^{N^{d}}(d<1)$ , we design an algorithm whose query complexity is $O(\sqrt{N\log M/\log N})$ and matches the lower bound proved in [4].(Hi) We can furthermore design a robust algorithm whose complexity changes smoothly between the complexity of (ii) and the complexity of recovering all information about the hidden oracle whose complexity is $O(N)$ as showed by Buhrman et.al. in [11].Thus our new algorithms are not only robust but also their query complexities are even better than the previous noiseless case [4],

Simon J. Devitt, William J. Munro, Kae Nemoto

Quantum error correction (QEC) and fault-tolerant quantum computation represent one of the most vital theoretical aspects of quantum information processing. It was well known from the early developments of this exciting field that the fragility of coherent quantum systems would be a catastrophic obstacle to the development of large-scale quantum computers. The introduction of quantum error correction in 1995 showed that active techniques could be employed to mitigate this fatal problem. However, quantum error correction and fault-tolerant computation is now a much larger field and many new codes, techniques, and methodologies have been developed to implement error correction for large-scale quantum algorithms. In response, we have attempted to summarize the basic aspects of quantum error correction and fault-tolerance, not as a detailed guide, but rather as a basic introduction. The development in this area has been so pronounced that many in the field of quantum information, specifically researchers who are new to quantum information or people focused on the many other important issues in quantum computation, have found it difficult to keep up with the general formalisms and methodologies employed in this area. Rather than introducing these concepts from a rigorous mathematical and computer science framework, we instead examine error correction and fault-tolerance largely through detailed examples, which are more relevant to experimentalists today and in the near future.

J. I. Cirac

レイモンド・H・プテラ, 一雄 岩間, 茂 山下

Mahn‐Soo Choi