product iamge

Classical and Quantum Computation

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Download
Search on Amazon

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

This book is an introduction to a new rapidly developing theory of quantum computing. It begins with the basics of classical theory of computation: Turing machines, Boolean circuits, parallel algorithms, probabilistic computation, NP-complete problems, and the idea of complexity of an algorithm. The second part of the book provides an exposition of quantum computation theory. It starts with the introduction of general quantum formalism (pure states, density matrices, and superoperators), universal gate sets and approximation theorems. Then the authors study various quantum computation algorithms: Grover's algorithm, Shor's factoring algorithm, and the Abelian hidden subgroup problem. In concluding sections, several related topics are discussed (parallel quantum computation, a quantum analog of NP-completeness, and quantum error-correcting codes).

Rapid development of quantum computing started in 1994 with a stunning suggestion by Peter Shor to use quantum computation for factoring large numbers--an extremely difficult and time-consuming problem when using a conventional computer. Shor's result spawned a burst of activity in designing new algorithms and in attempting to actually build quantum computers. Currently, the progress is much more significant in the former: A sound theoretical basis of quantum computing is under development and many algorithms have been suggested.

In this concise text, the authors provide solid foundations to the theory--in particular, a careful analysis of the quantum circuit model--and cover selected topics in depth. Included are a complete proof of the Solovay-Kitaev theorem with accurate algorithm complexity bounds, approximation of unitary operators by circuits of doubly logarithmic depth. Among other interesting topics are toric codes and their relation to the anyon approach to quantum computing.

Author(s): A. Yu. Kitaev, A. H. Shen, M. N. Vyalyi
Series: Graduate Studies in Mathematics
Publisher: Amer Mathematical Society
Year: 2002

Language: English
Pages: 258

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