CLASSICAL AND QUANTUM COMPUTATION

The book covers classical and quantum algorithms;-- of the 250 or so, pages of text, roughly the first 50 pages are "classical", the rest quantum;-- and indeed the aim of the book is to teach the wonders of the qubit-algorithms. While other books, such as Nielsen-Chuang, serve as (more or less)comprehensive references, the present book (by Kitaev et al) is focussed on complexity. The mathematical prerequisits are minimal, but a reader with some understanding of basic ideas from CS, and from quantum theory (at the level of ch 1 in Nielsen-Chuang), will get more out of Kitaev et al. The book is a translation of a Russian 1999 original, but it is really well done, and nicely updated;-- for example, a handy appendix was added, covering elementary math terms that are used.The book does a great job in explaining the fundamentals, both at the level of the *intuitive ideas*, as well as the mathematical proofs. The big question is why some qubit-algorithms (such as P Shor's factoring algorithm), are a lot better than classical counterparts(for example polynomial vs exponential), and a reader comes away with a good understanding of this in the end.Review by Palle Jorgensen, August 2003.