 Membership
 MAA Press
 Meetings
 Competitions
 Community
 Programs
 Students
 High School Teachers
 Faculty and Departments
 Underrepresented Groups
 MAA Awards
 MAA Grants
 News
 About MAA
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  SingleQubit Quantum Systems  9  
2.1  The Quantum Mechanics of Photon Polarization  9  
2.2  Single Quantum Bits  13  
2.3  SingleQubit Measurement  16  
2.4  A Quantum Key Distribution Protocol  18  
2.5  The State Space of a SingleQubit System  21  
2.6  References  25  
2.7  Exercises  26  
3  MultipleQubit Systems  31  
3.1  Quantum State Spaces  32  
3.2  Entangled States  38  
3.3  Basics of MultiQubit Measurement  41  
3.4  Quantum Key Distribution Using Entangled States  43  
3.5  References  44  
3.6  Exercises  44  
4  Measurement of MultipleQubit 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 PeriodFinding  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  FaultTolerant 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 NonAbelian Hidden Subgroup Problem  351  
B.6  References  351  
B.7  Exercises  352  
Bibliography  353  
Notation Index  365  
Index 