No label defined (Q4544834)

The main text is divided into two parts about classical computation (40 pages) and quantum computation (120 pages), followed by a part with solutions to selected exercises (70 pages) and an appendix on elementary number theory (10 pages). The first part on classical computation gives an introduction to computational complexity that covers deterministic, nondeterministic and probabilistic Turing machines and corresponding complexity classes defined in terms of time or space bounds, as well as Boolean circuits, reducibilities, the theory of NP-completeness, the hierarchy of complexity classes between P and PSPACE, including a couple of more advanced results like the containment of BPP in the second level of the polynomial hierarchy. This part is well readable and understandable, the treatment is elegant and essentially self-contained; the exposition is slightly terse and can probably only be used for an introductory course when occasionally adding technical details. The second part on quantum computation covers quantum circuits, quantum computation and the class BQP, quantum algorithms for the Abelian hidden subgroup problem, quantum NP-completeness, and quantum codes. \textit{R. De Wolf} points out in his review of the book [Quantum Inf. Comp. 1, 95-96 (2003)] that the part on quantum computation focusses on issues that are related to Kitaev's work in this area, giving a not fully self-contained but detailed and insightful exposition of these topics, which ``will provide the researcher with invaluable insights and tools for new research'', while, on the other hand, a considerable amount of more recent results and even some standard material in computer science aspects of quantum computation are missing, e.g., neither the Deutsch-Jozsa algorithm nor certain applications of Grover's algorithm are discussed.