To most people, the mysterious word “quantum” often means complex mathematics and advanced physics. This introductory book assumes basic linear algebra and no knowledge of quantum mechanics. The authors did an excellent job of introducing the model and presentations of quantum computing and describing the major quantum algorithms and their mathematical proofs in a straightforward yet rigorous way. Most of the chapters are self-contained.
After an introduction to the model of quantum computing in chapter 1, notations in chapter 2, and basic tools for linear algebra in chapter 3, the authors move to quantum-specific concepts, such as quantum feasibility, in chapter 4. Since the authors take the linear algebra approach, chapter 5 is devoted to the matrices used in quantum computing, such as Hadamard, Fourier, and permutation matrices. Before the discussion of quantum algorithms, the commonly used techniques, called “tricks” in the book, are summarized in chapter 6.
Although its title is “Phil’s Algorithm,” chapter 7 introduces three presentations of quantum algorithms: the maze diagram, matrix multiplication, and quantum circuit. Although the quantum circuit is the standard presentation, the maze diagram visualizes the quantum-mechanical effects of superposition and interference, and matrix presentation shows that quantum algorithms are actually matrix multiplications. This chapter provides a transition from the background to the quantum algorithms discussed in chapters 8 to 15. The authors start with the simple Deutsch’s algorithm to illustrate the characteristics of a quantum algorithm, namely superdense coding and teleportation and its analysis. Then, they gradually move to the more general Deutsch-Jozsa algorithm and Simon’s algorithm to show the significance of quantum computing. Although the simple Deutsch’s algorithm saves only one function evaluation from classical algorithms, Simon’s algorithm is significantly faster than any probabilistic classical algorithm for the same problem.
The famous Shor’s algorithm, one of the most important quantum algorithms for factoring integers in quantum polynomial time, is presented in chapters 11 and 12. Grover’s algorithm, in chapter 13, finds a special element (a needle) in a large set (haystack) in the order of the square root of the size of the set. Chapters 14 and 15 describe the more recent random walk algorithms and their applications. The quantum algorithm complexity BQP (short for bounded error quantum polynomial time) is discussed and compared with its counterpart, the classical BPP (bounded error probabilistic polynomial time) in chapter 16. Finally, chapter 17 includes some open problems and a philosophical discussion of quantum computing.
This is an excellent introductory book that can be used in a classroom, for self-study, or as a reference book. However, it could benefit from some improvements. For example, chapter 8 starts with the problem of finding a period of a function f that maps the natural numbers to the integers from 0 to M-1. In the first step of the strategy, the greatest common divisor of M and a random integer between 0 and M-1 is calculated. It then says that if the common divisor is nontrivial, we are done. It is unclear why we are done in this case, noticing that the problem here is to find a period of a function. Also, if the greatest common divisor is trivial, then the function fa(x) = ax mod M is formed. In the quantum part of the algorithm, the start vector is the functional superposition of f (page 100). It is unclear whether this f is the general mapping introduced in the beginning of the chapter or the particular fa defined in the first step of the strategy (page 97). Moreover, in chapter 12 on Shor’s algorithm for factoring integers (page 111), it would be more instructive if the precise assumptions on the integer M to be factored and the random integer a were explicitly stated. Actually, here we can say that we are done if the greatest common divisor of a and M is nontrivial, since the problem is to factor M.
I did enjoy reading this little book, as hoped by the authors. It opens a door to the fascinating field of quantum computing, and quantum algorithms in particular. I would recommend it to any computer science student or researcher who is curious about quantum algorithms.