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 .. 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.

2 Trace and Reduced Density Matrices ..487 The Bloch Sphere, No-Cloning Theorem andWiesner s Quantum Money The Bloch Sphere .. 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 .. 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.

3 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 .. 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 .. 13017 Quantum Query Complexity and The Deutsch-Josza Quantum Query Complexity .. Quantum Garbage Collection .. Deutsch s Algorithm .. Deutsch-Josza Algorithm.

4 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 .. 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 .. Applications of Grover s Algorithm.

5 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 .. 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.

6 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! To start with..Probability(P [0,1]) is the standard way of representing uncertainty inthe world. Probabilities have to follow certain axioms such as:IGiven a set ofnmutually exclusive exhaustive events, the sum of theprobabilities satisfiesP1+P2+ +Pn= 1 IThe probability of any particular event satisfiesPi 0..78 Lecture 1. COURSE Introduction AND THE ECTT here s a view that probabilities are all in our heads.

7 Which is to say that if we knew everything about the uni-verse (let s say position/velocity of all atoms in the solarsystem) that we could just crunch the equations and seethat things either happen or they don s suppose we have two points separated bya barrier with an open slit, and we want to measurethe probability that a particle goes from one point tothe other. It seems obviously true that increasing thenumber of paths (say, by opening another slit) shouldincrease, or at any rate not decrease, the likelihoodthat it will reach the other end. We refer to thisproperty by saying that probabilities the idea that things can only propagatethrough the universe at a certain speed. When weupdate the state of a little patch of space, it shouldonly require knowledge of a small neighborhood around it. Conway s GameOf Life (left) is a good model here: changes you make to the system can affectit, but since each cell only directly interacts with its nearest neighbors thechanges only propagate at a certain physics, locality naturally emerges due toEinstein s Special Theory of Relativity which im-plies that no signal can propagate faster thanthe (finite) speed of light; this simple princi-ple can explain a large number of physical phe-nomena.

8 In special relativity anything travel-ing faster than the speed of light would be ef-fectively traveling backwards in time, from someobserver s Realismis the principle that any in-stantaneous update in knowledge about faraway events can be explained bycorrelations of random variables. For example, if you in Austin and a friendin San Francisco both subscribe to the same newspaper then when you readyour copy in the morning your knowledge of the headline on your friend-in-San-Francisco s copy instantly collapses to whatever your copy s headline picking up the copy in the morning your knowledge of the headlinefor yourself and your friend may have been best described by a probability9distribution over various possibilities, but since the outcomes are perfectlycorrelated, as soon as you learn the headline on your copy you instantly knowthat your friend s must be the popular Science articles talk about how if you measurethe spin of one particle then instantaneously you can knowthe spin of another particle on the other side of the unless and until something more is said about it, that sno different from the case of the newspapers and seems100% compatible with local realism!

9 Church-Turing ThesisThe Church-Turing Thesis states that every phys-ical process can be simulated by a Turing machine to any desired way that Church and Turing understood this was as a definition of com-putation, but we can think of it instead as a falsifiable claim about the physicalworld. You can think about this as the idea that the entire universe is sort ofa gigantic video game: you ve got all sorts of complicated things, like quarksand black holes and whatnot, but at the end of the day you ve got to beable to simulate it on a computer. TheExtended Church-Turing Thesissays moreover that, when we simulate reality on a digital computer, there s atmost a polynomial ( , linear or quadratic) blowup in time, space, and othercomputational computer Science courses can be seen as basi-cally math courses. So what does connect them to reality?The Church-Turing , what does Quantum mechanics have to say about each of these princi-ples? To give you a teaser for much of the rest of the course:IWe ll still use probabilities.

10 But the way we llcalculateprobabilities willbe totally different, and will violate the axiom of monotonicity. That is,increasingthe number of ways for an event to happen, candecreasetheprobability that it will be upheld. ButLocal Realismwill be overthrown. Andif those two principles sounded like restatements of each other well, Quantum mechanics will dramatically illustrate the difference betweenthem!10 Lecture 1. COURSE Introduction AND THE ECTIAs we ll see, the Church-Turing Thesis still seems to be in good shape,even in light of Quantum mechanics, but the Extended Church-TuringThesis seems to be false, with Quantum computing standing as a glaringcounterexample to it possibly the one counterexample that our laws ofphysics allow. With that said, however, one can formulate a quantumversion of the Extended Church-Turing Thesis, which remains true asfar as anyone knows could imagine other possible counter-examples to theExtended Church-Turing Thesis.