Quantum Computing: A Gentle Introduction

First edition

Quantum Computing: A Gentle Introduction is a textbook on quantum computing. It was written by Eleanor Rieffel and Wolfgang Polak, and published in 2011 by the MIT Press.

Topics

Although the book approaches quantum computing through the model of quantum circuits, it is focused more on quantum algorithms than on the construction of quantum computers. It has 13 chapters, divided into three parts: "Quantum building blocks" (chapters 1–6), "Quantum algorithms" (chapters 7–9), and "Entangled subsystems and robust quantum computation" (chapters 10–13).

After an introductory chapter overviewing related topics including quantum cryptography, quantum information theory, and quantum game theory, chapter 2 introduces quantum mechanics and quantum superposition using polarized light as an example, also discussing qubits, the Bloch sphere representation of the state of a qubit, and quantum key distribution. Chapter 3 introduces direct sums, tensor products, and quantum entanglement, and chapter 4 includes the EPR paradox, Bell's theorem on the impossibility of local hidden variable theories, as quantified by Bell's inequality. Chapter 5 discusses unitary operators, quantum logic gates, quantum circuits, and functional completeness for systems of quantum gates. Chapter 6, the final chapter of the building block section, discusses (classical) reversible computing, and the conversion of arbitrary computations to reversible computations, a necessary step to performing them on quantum devices.

In the section of the book on quantum algorithms, chapter 7 includes material on quantum complexity theory and the Deutch algorithm, Deutsch–Jozsa algorithm, Bernstein–Vazirani algorithm, and Simon's algorithm, algorithms devised to prove separations in quantum complexity by solving certain artificial problems faster than could be done classically. It also covers the quantum Fourier transform. Chapter 8 covers Shor's algorithm for integer factorization, and introduces the hidden subgroup problem. Chapter 9 covers Grover's algorithm and the quantum counting algorithm for speeding up certain kinds of brute-force search. The remaining chapters return to the topic of quantum entanglement and discuss quantum decoherence, quantum error correction, and its use in designing robust quantum computing devices, with the final chapter providing an overview of the subject and connections to additional topics. Appendices provide a graphical approach to tensor products of probability spaces, and extend Shor's algorithm to the abelian hidden subgroup problem.

Audience and reception

The book is suitable as an introduction to quantum computing for computer scientists, mathematicians, and physicists, requiring of them only a background in linear algebra and the theory of complex numbers, although reviewer Donald L. Vestal suggests that additional background in the theory of computation, abstract algebra, and information theory would also be helpful. Prior knowledge of quantum mechanics is not required.

Reviewer Kyriakos N. Sgarbas has some minor notational quibbles with the book's presentation, and complains that the level of difficulty is uneven and that it lacks example solutions. However, reviewer Valerio Scarani calls the book "a masterpiece", particularly praising it for its orderly arrangement, its well-thought-out exercises, the self-contained nature of its chapters, and its inclusion of material warning readers against falling into common pitfalls.

Related works

There are many other textbooks on quantum computing; for instance, Scarani lists Quantum Computer Science: An Introduction by N. David Mermin (2007), An Introduction to Quantum Computing by Kaye, Laflamme, and Mosca (2007), and A Short Introduction to Quantum Information and Quantum Computation by Michel Le Bellac (2006). Sgarbas lists in addition Quantum Computing Explained by D. McMahon (2008) and Quantum Computation and Quantum Information by M. A. Nielsen and I. L. Chuang (2000).