You are here

Quantum Algorithms via Linear Algebra

Richard J. Lipton and Kenneth W. Regan
MIT Press
Publication Date: 
Number of Pages: 
[Reviewed by
Tushar Das
, on

The celebrated theoretical computer scientist Richard J. Lipton (winner of the 2014 Knuth prize) and Kenneth W. Regan (an International Master among chess professionals) have conjured up an attractive slim volume on quantum algorithms. The realization/construction/implementation of computers that operate in the quantum regime seems far away today, so theirs is a purely theoretical book. In the first 100 pages or so, one finds the skeleton of a 10-to-12-week undergraduate course aimed at computer science majors who have had a taste of algorithms and computation. More advanced courses or seminars could sample from the later chapters on more sophisticated topics. The entire book is just over 200 pages, a remarkable feat given its contents.

Quantum Algorithms via Linear Algebra starts with a rapid introduction to the necessary language and formalism, goes on to describe the seminal ideas in this area, due to Feynman and Deutsch in the 1980s, then follows with a chapter each on the groundbreaking algorithms of Simon, Shor and Grover, and ends with brief introduction to two present-day research fields: quantum walk search algorithms and quantum complexity theory.

The authors have a strictly no-nonsense, or no-physics, approach to the subject. The reader will find practically no discussion of quantum physics, neither at the operational level nor its multifarious vagaries (e.g., entanglement, EPR, Bell, cats, the lot). For a book on quantum algorithms there is little development of the theory of quantum gates and circuits in any detail. Even Dirac’s wonderful bra-kets have been thrown out of the party (for the most part). The advantage of the no-nonsense approach, i.e., of steering clear of any quantum content, is that the authors can focus all their attention on exposing the bare minimum of linear-algebraic, combinatorial and number-theoretic techniques that are required to describe a variety of key quantum algorithms in the briefest possible way. The Lipton-Regan philosophy is that quantum computations are best taught and thought of initially as actions of unitary matrices on the unit sphere of a complex Hilbert space, and not via quantum circuits and quantum gates. E.g. a quantum program, for them, is nothing more than a composition of unitary matrices.

A few semesters ago, this reviewer was on the lookout for a self-contained textbook that could lead an independent study with a math major interested in learning about quantum computing and quantum information theory. The book recommended (deemed by a number of individuals in mathematics, physics and computer science as the gold standard) was Michael A. Nielsen and Isaac L. Chuang’s Quantum Computation and Quantum Information (10th Anniversary Edition, Cambridge, 2010). Possibly the only downside of Nielsen-Chang is that it is close to 700 pages, and therefore necessitates a non-trivial amount of guidance to help the student achieve something meaningful within a semester. In fact, the authors of the slim book under review often refer the reader to the bulkier Nielsen-Chang ”for more details.“ Unlike Nielsen-Chang, the authors follow ”ISO/IEC standards of bold lowercase italic for vectors and bold uppercase italic for matrices, in heavier, less-serifed fonts” which are somewhat painful to this reviewer’s eyes. Nevertheless, such notation may well be the norm in CS departments.

This book seems most suitable for study by a senior or graduate seminar within a CS department. Lipton-Regan give a bird’s-eye view, deftly delineating ideas behind arguments and algorithms, sketching implementations, and leaving readers to flesh out most of the gory details, though often via attractive exercise sets. Undergraduate math majors attempting this book without a background in computation and algorithms may find their treatment to be challenging at best, and cookbook at worst. Students who do have some of this background would surely find this to be an exciting text.

Tushar Das is an Assistant Professor of Mathematics at the University of Wisconsin–La Crosse.

The table of contents is not available.