|
|
|
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 |