You are here

Quantum Computing: A Gentle Introduction

Eleanor Rieffel and Wolfgang Polak
Publisher: 
MIT Press
Publication Date: 
2011
Number of Pages: 
372
Format: 
Hardcover
Price: 
45.00
ISBN: 
9780262015066
Category: 
Textbook
[Reviewed by
Donald L. Vestal
, on
08/6/2012
]

According to the preface: “This book is concerned with theory: what changes when the classical model underpinning conventional computing is replaced with a quantum one.” So the classical bit is replace by the quantum bit (or “qubit”) and the classical operations are turned into quantum operations. The authors spend much time covering quantum algorithms, most notably Shor’s algorithm, quantum entanglement, and robustness.

If you want to learn about quantum computing, this is a good source. Is it “gentle”? Well, maybe as gentle as a book of this nature can be, which is not much. But it is rigorous — the necessary theory is laid out, along with a lot of exercises for practice. If you want to get the most out of this text, you’ll need a solid foundation in computing and linear algebra; and some additional background in abstract algebra and information theory wouldn’t hurt.


Donald L. Vestal is an Associate Professor of Mathematics at South Dakota State University. His interests include number theory, combinatorics, spending time with his family, and working on his hot sauce collection. He can be reached at Donald.Vestal(AT)sdstate.edu.




1 Introduction 1

I QUANTUM BUILDING BLOCKS

2 Single-Qubit Quantum Systems 9


     2.1 The Quantum Mechanics of Photon Polarization 9


     2.2 Single Quantum Bits 13


     2.3 Single-Qubit Measurement 16


     2.4 A Quantum Key Distribution Protocol 18


     2.5 The State Space of a Single-Qubit System 21


     2.6 References 25


     2.7 Exercises 26

3 Multiple-Qubit Systems 31


     3.1 Quantum State Spaces 32


     3.2 Entangled States 38


     3.3 Basics of Multi-Qubit Measurement 41


     3.4 Quantum Key Distribution Using Entangled States 43


     3.5 References 44


     3.6 Exercises 44

4 Measurement of Multiple-Qubit States 47


     4.1 Dirac’s Bra/Ket Notation for Linear Transformations 47


     4.2 Projection Operators for Measurement 49


     4.3 Hermitian Operator Formalism for Measurement 53


     4.4 EPR Paradox and Bell’s Theorem 60


     4.5 References 65


     4.6 Exercises 66

5 Quantum State Transformations 71


     5.1 Unitary Transformations 72


     5.2 Some Simple Quantum Gates 74


     5.3 Applications of Simple Gates 80


     5.4 Realizing Unitary Transformations as Quantum Circuits 84


     5.5 A Universally Approximating Set of Gates 91


     5.6 The Standard Circuit Model 93


     5.7 References 93


     5.8 Exercises 94

6 Quantum Versions of Classical Computations 99


     6.1 From Reversible Classical Computations to Quantum Computations 99


     6.2 Reversible Implementations of Classical Circuits 103


     6.3 A Language for Quantum Implementations 110


     6.4 Some Example Programs for Arithmetic Operations 115


     6.5 References 120


     6.6 Exercises 121

II QUANTUM ALGORITHMS

7 Introduction to Quantum Algorithms 125


     7.1 Computing with Superpositions 126


     7.2 Notions of Complexity 130


     7.3 A Simple Quantum Algorithm 132


     7.4 Quantum Subroutines 134


     7.5 A Few Simple Quantum Algorithms 140


     7.6 Comments on Quantum Parallelism 146


     7.7 Machine Models and Complexity Classes 148


     7.8 Quantum Fourier Transformations 153


     7.9 References 158


     7.10 Exercises 159

8 Shor’s Algorithm 163


     8.1 Classical Reduction to Period-Finding 164


     8.2 Shor’s Factoring Algorithm 164


     8.3 Example Illustrating Shor’s Algorithm 167


     8.4 The Efficiency of Shor’s Algorithm 169


     8.5 Omitting the Internal Measurement 170


     8.6 Generalizations 171


     8.7 References 175


     8.8 Exercises 176

9 Grover’s Algorithm and Generalizations 177


     9.1 Grover’s Algorithm 178


     9.2 Amplitude Amplification 183


     9.3 Optimality of Grover’s Algorithm 188


     9.4 Derandomization of Grover’s Algorithm and Amplitude Amplification 193


     9.5 Unknown Number of Solutions 196


     9.6 Practical Implications of Grover’s Algorithm and Amplitude Amplification 199


     9.7 References 200


     9.8 Exercises 201

III ENTANGLED SUBSYSTEMS AND ROBUST QUANTUM COMPUTATION 203

10 Quantum Subsystems and Properties of Entangled States 205


     10.1 Quantum Subsystems and Mixed States 206


     10.2 Classifying Entangled States 218


     10.3 Density Operator Formalism for Measurement 229


     10.4 Transformations of Quantum Subsystems and Decoherence 232


     10.5 References 240


     10.6 Exercises 240

11 Quantum Error Correction 245


     11.1 Three Simple Examples of Quantum Error Correcting Codes 246


     11.2 Framework for Quantum Error Correcting Codes 253


     11.3 CSS Codes 274


     11.4 Stabilizer Codes 280


     11.5 CSS Codes as Stabilizer Codes 289


     11.6 References 290


     11.7 Exercises 291

12 Fault Tolerance and Robust Quantum Computing 293


     12.1 Setting the Stage for Robust Quantum Computation 294


     12.2 Fault-Tolerant Computation Using Steane’s Code 297


     12.3 Robust Quantum Computation 305


     12.4 References 310


     12.5 Exercises 310

13 Further Topics in Quantum Information Processing 311


     13.1 Further Quantum Algorithms 311


     13.2 Limitations of Quantum Computing 313


     13.3 Further Techniques for Robust Quantum Computation 314


     13.4 Alternatives to the Circuit Model of Quantum Computation 316


     13.5 Quantum Protocols 320


     13.6 Insight into Classical Computation 321


     13.7 Building Quantum Computers 322


     13.8 Simulating Quantum Systems 325


     13.9 Where Does the Power of Quantum Computation Come From? 326


     13.10 What if Quantum Mechanics Is Not Quite Correct? 327



  APPENDIXES 329

A Some Relations Between Quantum Mechanics and Probability Theory 331


     A.1 Tensor Products in Probability Theory 331


     A.2 Quantum Mechanics as a Generalization of Probability Theory 337


     A.3 References 339


     A.4 Exercises 339

B Solving the Abelian Hidden Subgroup Problem 341


     B.1 Representations of Finite Abelian Groups 341


     B.2 Quantum Fourier Transforms for Finite Abelian Groups 345


     B.3 General Solution to the Finite Abelian Hidden Subgroup Problem 348


     B.4 Instances of the Abelian Hidden Subgroup Problem 350


     B.5 Comments on the Non-Abelian Hidden Subgroup Problem 351


     B.6 References 351

B.7 Exercises 352

Bibliography 353

Notation Index 365

Index