Sunday, January 14, 2007

Quantum information

Here's a really good book on quantum computing. If you want to read something on the subject just go for this no-nonsense, good math, just around a hundred pages of all you ever wanted to know about Alice and Bob, entanglement, teleportation, the Shor algorithm, entropy and information and all that. The text is based on a series of lectures delivered by the author at the Tata Institute of Fundamental Research in Mumbai and published by the Indian science publisher Narosa.

K R Parthasarathy adopts the typical excellent style of most Indian mathematician: always crystal clear, essential and to the point. Good mathematics, well presented, and decorated with a very good choice of examples and exercises for the reader. The text begins with a comparison table between classical and quantum probability theory. Assuming the reader is familiar with the classical notions, the table presents in a very concise manner all the main characters of the book from the very beginning and one immediately starts to develop the right feeling for why quantum probability is different. The second lecture is dedicated the theory of quantum circuits and the computation of quantum logical gates. For someone like me how had a childhood passion for the computation of classical circuits and logical gates this chapter was a lot of fun to read. The main idea that is conveyed right at the start is that quantum gates are given by unitary operators and as such (unlike classical gates like AND) they are always invertible. One learns how to construct quantum circuits that simulate a Markov chain, the case of one q-bit gates like those given by the Pauli matrices, two q-bits gates like the CNOT (controlled NOT) and an assortment of three q-bit gates with which one quickly learns how to do calculations. The teleportation argument is then explained in full as a simple application of the calculus of quantum gates just introduced. This is the clearest and simplest explanation I have found so far. Coding and quantum communication via EPR pairs is explained in much the same style.

The following lecture discusses the universal property of the CNOT and the one q-bit gates using decompositions of unitary matrices as a product of a phase factor and 2-dimensional unitary matrices. A very nice twist in this story is the use of algebraic results on the ring of integer polynomials to prove a density argument for the angles of rotation matrices that is used to prove that any 2-dimensional unitary can be approximated by a combination of the Hadamard gate, the CNOT, and the previously discussed pi/8 gates.

Lecture 4 is dedicated to the quantum Fourier transform on finite dimensional Hilbert spaces and the estimation of phase in quantum computing. Lecture 5 describes how to use quantum computing and the phase estimation procedure to solve the problem of finding the order of an invertible element in a finite cyclic group using only a polynomial number of gates. The chapter also describes how non-reversible classical gates like AND or OR can be modelled via a reversible quantum gate with extra wires, so that the result of the classical gate appears on a subset of the wires involved.
Lecture 6 is dedicated to the famous Shor algorithm for factorization into primes. At this point, after the previous lectures, this can be explained very simply in just a few pages. Lecture 7 described quantum error correcting codes and generalized Shor algorithms. Lectures 8 and 9 conclude the book with a quite beautiful exposition of Shannon's information theory and of von Neumann entropy in quantum information.

I encouraged anyone who is curious about quantum computing to go straight to this book, which can be read from first page to last in just about three or four hours (the span of a long train ride on TGV or ICE lines) and gives you direct access to the real stuff with minimal effort.