iv Contents
5. The hierarchy of complexity classes 44
5.1. Games machines play 44
5.2. The class PSPACE 48
Part 2. Quantum Computation 53
6. Definitions and notation 54
6.1. The tensor product 54
6.2. Linear algebra in Dirac’s notation 55
6.3. Quantum gates and circuits 58
7. Correspondence between classical and quantum computation 60
8. Bases for quantum circuits 65
8.1. Exact realization 65
8.2. Approximate realization 71
8.3. Efficient approximation over a complete basis 75
9. Definition of Quantum Computation. Examples 82
9.1. Computation by quantum circuits 82
9.2. Quantum search: Grover’s algorithm 83
9.3. A universal quantum circuit 88
9.4. Quantum algorithms and the class BQP 89
10. Quantum probability 92
10.1. Probability for state vectors 92
10.2. Mixed states (density matrices) 94
10.3. Distance functions for density matrices 98
11. Physically realizable transformations of density matrices 100
11.1. Physically realizable superoperators: characterization 100
11.2. Calculation of the probability for quantum computation 102
11.3. Decoherence 102
11.4. Measurements 105
11.5. The superoperator norm 108
12. Measuring operators 112
12.1. Definition and examples 112
12.2. General properties 114
12.3. Garbage removal and composition of measurements 115
13. Quantum algorithms for Abelian groups 116
Previous Page Next Page