Introduction to Quantum Information Science Lecture Notes

1 Introduction to Quantum Information ScienceLecture NotesScott Aaronson1 Fall 20181 With crucial help from: Corey Ostrove and Paulo AlvesContentsPage1 Course Introduction and The ExtendedChurch-Turing Thesis72 Probability Theory and Quantum Linear Algebra Approach to Probability Theory ..153 Basic Rules of Quantum Quantum States and The Ket Notation .. Transforming Quantum States .. Quantum Interference .. and Relative Phase ..234 Quantum Gates and Circuits, Quantum Zenoand The Elitzur-Vaidman Quantum Gates.

2 Born Rule .. Properties of Quantum Gates and Measurements Quantum Circuit Notation .. Quantum Zeno Effect .. The Elitzur-Vaidman Bomb ..325 The Coin Problem, Distinguishability, Multi-Qubit Statesand The Coin Problem .. Distinguishability of Quantum States .. Multi-Qubit States and Operations .. Operations ..402 CONTENTS36 Mixed Mixed States .. Matrices .. of Density Matrices .. Trace and Reduced Density Matrices ..487 The Bloch Sphere, No-Cloning Theorem andWiesner s Quantum Money The Bloch Sphere.

3 Gates in the Bloch Sphere Representation .. The No-Cloning Theorem .. Quantum Money .. s Quantum Money Scheme ..578 Quantum Money and Quantum Key Quantum Money Attacks .. Attacks .. Quantum Money .. Quantum Key Distribution ..629 Superdense Superdense Coding ..6610 Teleportation, Entanglement Swapping, GHZ Stateand The Monogamy of Quantum Teleportation .. Multi-Qubit Teleportation and Entanglement The GHZ State and Monogamy of Entanglement ..7311 Quantifying Schmidt Decomposition.

4 Von Neumann Entropy .. Entanglement Entropy .. Mixed State Entanglement ..8012 Interpretations of Quantum The Copenhagen Interpretation .. Shut Up and Calculate .. Schr odinger s Cat and Wigner s Friend .. Dynamical Collapse .. Ghirardi-Rimini-Weber (GRW) Theory .. Penrose Theory .. The Many-Worlds Interpretation ..9113 Hidden Variables and Bell s Hidden Variable Theories .. Bohmian Mechanics .. Local Hidden Variable Theories .. The CHSH Game .. 10014 Nonlocal CHSH Game: Quantum Strategy.

5 Analysis of Protocol .. CHSH Game: Interpretations and Local Realism .. Tsirelson s Inequality .. Experimental Tests of Bell s Inequalities .. The Odd Cycle Game .. The Magic Square Game .. 11415 Einstein-Certified Guaranteed Random Numbers .. Leashing Quantum Systems .. 12016 Quantum Computing and Universal Gate Complexity of General Unitaries: Counting Argument .. Universal Gate Sets .. Classical Universality .. Quantum Universality .. The Solovay-Kitaev Theorem.

6 13017 Quantum Query Complexity and The Deutsch-Josza Quantum Query Complexity .. Quantum Garbage Collection .. Deutsch s Algorithm .. Deutsch-Josza Algorithm .. 13918 Bernstein-Vazirani and Simon s The Bernstein-Vazirani Problem .. Quantum Algorithm .. Simon s Problem .. Classical Lower Bound .. Quantum Algorithm .. 147 CONTENTS519 RSA and Shor s RSA Encryption .. Period Finding .. Factoring to Period-Finding Reduction .. Quantum Algorithm for Period-Finding.

7 15720 Quantum Fourier Quantum Fourier Transform .. Implementing the QFT .. Period Finding Using the QFT .. 16521 Continued Fractions and Shor s Algorithm Continued Fraction Algorithm .. Applications of Shor s Algorithm .. Graph Isomorphism .. Lattice-Based Cryptography .. 17322 Grover s The Algorithm .. Implementing the Diffusion Operator .. Geometric Interpretation .. Analysis .. Multiple Marked Items .. 18523 BBBV Theorem and Applications of Grover s The BBBV Theorem.

8 Applications of Grover s Algorithm .. OR of ANDs .. 19524 More Grover Applications and Quantum Complexity More Applications of Grover s Algorithm .. The Collision Problem .. Element Distinctness .. Parity Lower Bound .. Quantum Complexity Theory .. 20425 Quantum Algorithms forNP-complete Problems .. Hamiltonians .. Matrix Exponentiation .. Energy .. Tensor Products of Hamiltonians .. Addition of Hamiltonians .. 21626 The Adiabatic Local Hamiltonians.

9 The Adiabatic Algorithm .. 22327 Quantum Error Classical Error Correction .. Classical Fault-Tolerance .. Quantum Error Correction .. The Shor 9-Qubit Code .. Quantum Fault Tolerance .. 24728 The Stabilizer The Gottesman-Knill Theorem .. The Gottesman-Knill Algorithm .. Stabilizer Codes .. Transversal Gates .. 259 Lecture 1: Course Introductionand The Extended Church-TuringThesisIQuantum Information Science is an inherently interdisciplinary field (Physics,CS, Math, Engineering, Philosophy)IIt s not just about inventing useful devices and algorithms, but alsoabout clarifying the workings of Quantum mechanics.

10 We use it to ask questions about what you can and can t do withquantum mechanics It can help us better understand the nature of Quantum Aaronson is very much on the theoretical end of inform what experimentalists make, which in turn informs the-orists queriesToday we ll articulate several self-evident statements about the physicalworld. We ll then see that Quantum mechanics leaves some of these statementsin place, but overturns others with the distinctions between the statementsit upholds and the ones it overturns often extremely subtle!