Classical and Quantum Computation

Contents......Page 4
Notation......Page 9
1. Turing machines......Page 13
1.1. Definition of a Turing machine......Page 14
1.2. Computable functions and decidable predicates......Page 15
1.3. Turing's thesis and universal machines......Page 16
1.4. Complexity classes......Page 18
2.1. Definitions. Complete bases......Page 21
2.2. Circuits versus Turing machines......Page 24
2.3. Basic algorithms. Depth, space and width......Page 27
3.1. Nondeterministic Turing machines......Page 31
3.2. Reducibility and NP-completeness......Page 34
4.1. Definitions. Amplification of probability......Page 40
4.2. Primality testing......Page 42
4.3. BPP and circuit complexity......Page 46
5.1. Games machines play......Page 48
5.2. The class PSPACE......Page 52
Part 2. Quantum Computation......Page 56
6.1. The tensor product......Page 57
6.2. Linear algebra in Dirac's notation......Page 58
6.3. Quantum gates and circuits......Page 61
7. Correspondence between classical and quantum computation......Page 63
8.1. Exact realization......Page 68
8.2. Approximate realization......Page 74
8.3. Efficient approximation over a complete basis......Page 78
9.1. Computation by quantum circuits......Page 85
9.2. Quantum search: Grover's algorithm......Page 86
9.3. A universal quantum circuit......Page 91
9.4. Quantum algorithms and the class BQP......Page 92
10.1. Probability for state vectors......Page 95
10.2. Mixed states (density matrices)......Page 97
10.3. Distance functions for density matrices......Page 101
11.1. Physically realizable superoperators: characterization......Page 103
11.3. Decoherence......Page 105
11.4. Measurements......Page 108
11.5. The superoperator norm......Page 111
12.1. Definition and examples......Page 115
12.2. General properties......Page 117
12.3. Garbage removal and composition of measurements......Page 118
13. Quantum algorithms for Abelian groups......Page 119
13.1. The problem of hidden subgroup in (Z_2)^k; Simon's algorithm......Page 120
13.2. Factoring and finding the period for raising to a power......Page 122
13.3. Reduction of factoring to period finding......Page 123
13.4. Quantum algorithm for finding the period: the basic idea......Page 125
13.5. The phase estimation procedure......Page 128
13.6. Discussion of the algorithm......Page 133
13.7. Parallelized version of phase estimation. Applications......Page 134
13.8. The hidden subgroup problem for Z^k......Page 138
14.1. Modification of classical definitions......Page 141
14.2. Quantum definition by analogy......Page 142
14.3. Complete problems......Page 144
14.4. Local Hamiltonian is BQNP-complete......Page 147
14.5. The place of BQNP among other complexity classes......Page 153
15. Classical and quantum codes......Page 154
15.1. Classical codes......Page 156
15.2. Examples of classical codes......Page 157
15.3. Linear codes......Page 158
15.4. Error models for quantum codes......Page 159
15.5. Definition of quantum error correction......Page 161
15.6. Shor's code......Page 164
15.7. The Pauli operators and symplectic transformations......Page 166
15.8. Symplectic (stabilizer) codes......Page 170
15.9. Toric code......Page 173
15.10. Error correction for symplectic codes......Page 175
15.11. Anyons (an example based on the toric code)......Page 176
S1. Problems of Section 1......Page 179
S2. Problems of Section 2......Page 185
S3. Problems of Section 3......Page 197
S5. Problems of Section 5......Page 204
S6. Problems of Section 6......Page 205
S8. Problems of Section 8......Page 206
S9. Problems of Section 9......Page 218
S10. Problems of Section 10......Page 223
S11. Problems of Section 11......Page 226
S13. Problems of Section 13......Page 232
S15. Problems of Section 15......Page 236
A.1. Modular arithmetic and rings......Page 238
A.2. Greatest common divisor and unique factorization......Page 240
A.3. Chinese remainder theorem......Page 242
A.4. The structure of finite Abelian groups......Page 244
A.5. The structure of the group (Z/qZ)^*......Page 246
A.6. Euclid's algorithm......Page 248
A.7. Continued fractions......Page 249
Bibliography......Page 252
Index......Page 256