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. Eﬃcient 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