


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 