Quantum Computation and Quantum Information

The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. This question cannot be separated from that of quantum complexity, because any realistic model will inevitably be subject to such inaccuracies. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics. Fundamental Concepts Introduction and overview Introduction to quantum mechanics Introduction to computer science Quantum Computation Quantum circuits The quantum Fourier transform and its applications Quantum search algorithms Quantum computers: physical realisation Quantum Information Quantum noise, open quantum systems, and quantum operations Distance measurement for quantum information Quantum error-correction Entropy and information Quantum information theory Notes on basic probability theory Group theory Approximating quantum gates: the Solovay-Kitaev theorem Number theory Public-key cryptography and the RSA cryptosystem Proof of Lieb's theorem.