Quantum walks and search algorithms (Q5917872)

Quantum computing is an unconventional computational paradigm in which the classical computing models, like Turing machines, are replaced by new computational models inspired by quantum mechanics principles. As the author of the reviewed book points out, ``information storage, processing and transmission obeying quantum mechanical laws allowed the development of new algorithms, faster than the classical analogues''. Research on quantum computing topics is rather intense, both in terms of theoretical computer science, where one is traditionally interested in computability and complexity, but also in terms of physics, as in this setting the computational environment is the physics lab, and building the hardware on which quantum algorithms may run is an important engineering challenge. The reviewed book is a pedagogically oriented survey of the main results regarding quantum walks and quantum search algorithms. Basically, quantum walks correspond, in terms of quantum computing, to the classical random walks, and, just like in the classical case, there are either discrete-time or continuos time walks. However, the properties of quantum walks are very different from those of their classical counterpart. Understanding quantum walks is essential in quantum computing, as they play an important role in the development of efficient quantum algorithms. For instance, the best algorithm solving the element distinctness problem is based on quantum walks. Search algorithms are among the core topics of classical computer science. Similarly, quantum search algorithms are important topics in quantum computing. For instance, Grover's algorithm is one of the essential quantum search algorithms, solving efficiently the problem of finding an element in an unsorted database, and having also a wider range of applicability. The importance of Grover's algorithm is amplified by the fact that it introduces the amplitude amplification, a method used in many other efficient quantum algorithms. Moreover, Grover's algorithm can also described as a quantum walk on complete graphs. These are only shallow remarks on the importance of these two concepts in quantum computing, that motivate their deeper study. The reviewed book also starts with a basic introduction in quantum walks and a presentation of Grover's algorithm, but then goes indeed deeper in both these topics, offering an overview of the many ideas and tools needed for more thorough understanding of the described concepts. The book is structured in nine chapters and one appendix. The first Chapter is a brief introduction in quantum computing, while the second Chapter presents the postulates of quantum mechanics. As the author points out, the second Chapter and the appendix, which deals with basic linear algebra concepts and results, are fundamental in understanding the rest of the book. The third and fourth Chapter present introductory facts on quantum walks and Grover's algorithm, respectively; at the end of the fourth Chapter the details of the amplitude amplification method are given. The fifth and sixth Chapters of the book deal with quantum walks on important infinite and, respectively, finite graphs: lines, cycles, two-dimensional lattices, or hypercubes. The first six chapters are easier to grasp than the rest of the book, and offer a solid basis for the area of quantum walks and search algorithms. The seventh Chapter of the book deals with quantum walks on generic graphs and presents methods to calculate the limiting probability distribution (again, in cycles, hypercubes or finite lattices) and the mixing time. Chapter eight is on spatial search algorithms, describing a technique called abstract search algorithm. Chapter nine presents Szegedy's quantum walk model and basic facts regarding the quantum hitting time. In order to follow the more involved facts presented in Chapters seven, eight, and nine a good understanding of the concepts presented in the previous chapters is needed. In my opinion the reviewed material is a rather good textbook on quantum walks and search algorithms, but I am not an expert in the area. The book is nicely written, the concepts are introduced naturally, and many meaningful connections between them are highlighted. The author proposes a series of exercises that help the reader get some working experience with the presented concepts, facilitating a better understanding. Each chapter ends with a discussion of further references, pointing the reader to major results on the topics presented in the respective chapter. As the author emphasises, the book is followed easier by people that posses both basic knowledge of classical computability, complexity, and algorithmics as well as basic understanding of quantum mechanics and some knowledge of quantum computing.