UNM Physics 452/581: Introduction to Quantum Information

Announcements and updates

Mon Dec 17 Congratulations to the entire class for a job well done. We covered a wide range of challenging material in a short time, and everyone did well on the problem sets and Wikipedia projects. I encourage each of you to copy your Wikipedia articles from our local server to the global Wikipedia---it would be a great service to the community. Once there, be aware that it may be ruthlessly edited. That said, Wikipedia is in desparate need of your content, and it would be valued greatly. Have a great holiday!
Sat Nov 24 Minor corrections to Problem set 6: corrected spelling of tintinnabulation, changed problems to start with "6," not "5," normalized Kraus operators in Extra Credit problem 6.7(a), and dropped superfluous "p" subscripts in Kraus operators of problem 6.5(e).
M Nov 12 Problem set 6 is now available. It has five problems and two extra credit problems, but I'm giving you all over two weeks to finish it---it's due the Tuesday after Thanksgiving. Also, here is a link to the directions for the Wikipedia project that I e-mailed to the class. Please submit your proposals for a wiki article to me by this Thursday.
Tu Oct 9 Problem set 5 is due Thursday, Oct. 18; I had originally listed the nonexistent date of Thursday, Oct. 16; even though the set only has two problems, there is Fall break in between so that you should still have a full week of non-holiday time to work on it. Remember: No class next Thursday or Tuesday.
W Oct 3 Extension: Problem set 4 will be due Tuesday, Oct. 9 instead of Thursday, Oct. 4. That should also get us back on track; had I given a week-long problem set this Thursday, it could not be due the following Thursday because that is a UNM Holiday.
W Oct 3 Students seem to having particular difficulty with problem 4.2(b). I've added a further hint to the problem that reminds that it is the worst-case input that is relevant when calculating the complexity of the algorithm.
M Oct 1 Another minor update to Problem set 4: the hint for problem 4.3(e) should state that the trace of a matrix times a Pauli operator yields 2^n times the corresponding Pauli coefficent of the matrix.
M Oct 1 Minor update to Problem set 4: the base of the logarithm in problem 4.2(c) should be k, not 2.
W Sep 26 I've posted Problem set 4 and I've extended its deadline to next Thursday instead of next Tuesday.
M Sep 17 The material we've been discussing lately hasn't really lended itself to a good problem set, so I'm going to skip handing out a problem set for this week. As I said on the first day of classes, I plan on handing out problem sets roughly weekly, but I'm not a slave to that.

That of course gives at least two options for how to handle the assignment due on Tuesday (tomorrow). The first is to make it still be due tomorrow so that the remainder of the week nobody has to think about an IQI problem set. The other is to have the problem set be due the following Tuesday (9/25), giving students more time to work on the problems and polish their answers. Given that a number of students have expressed some difficulty with this problem set, I've decided to take the latter course. I'd much rather have the class understand a few problems well than many problems hardly at all. So please, if you have questions about this problem set in the upcoming week, I encourage you to stop by my office hours or send an e-mail requesting a meeting at another time.
M Sep 17 For problem 3.1(d), the angle should be 2*pi/3, not pi/3. You'll get full credit if you work out either angle, but the 2*pi/3 angle is much easier to work with and has a simpler geometric interpretation. I also added hints to problems 3.1(a) and 3.2(b), for those of you needing a jump-start.
W Sep 12 I've added the third problem to Problem set 3; there will be no extra credit problem this week.
W Sep 12 Problem set 3 has now been posted; the third problem and extra credit problem still need to be added, but the current problems should keep you busy until then.
Sat Sep 8 Typed-up lecture notes for lecture 6 are now available.
F Sep 7 Extra credit problem 2.4: Bob doesn't have to reverse his "reveal" strategy relative to Alice's as originally indicated; PS 2 amended to indicate this.
Th Sep 6 Problem 2.3(c) should evaluate to 80.18%; I added an extra credit problem describing an even better strategy that achieves the optimal 85.35% success rate for the game.
W Sep 5 Minor type-os have been fixed in problems 2.2(e) and 2.2(g), notation has been clarified for 2.2(g) and 2.2(i). I have also made clearer what is being asked for problems 2.2(d) and 2.3(a).
W Sep 5 I have posted scanned-in versions of my notes from lectures 3 to 5. They are really rough (esp. lecture 4); I hope to get them typed up soon.
W Sep 5 Problem set 2 has now been posted. I generally won't use this announcement section to indicate that a problem set has been posted; please just check the course calendar section at the bottom of the web page shortly after a previous problem set has been handed in and a new problem set should appear.
F Aug 31 Problem set 1 has been reposted again, with yet further clarifications, corrected problem numbers, and a new set of probability values to use for problem 1.2. These are the numbers I meant to use, but constant cutting-and-pasting caused me to flip-flop some of them. Sorry for the bugs in this first problem set! Future assignments should be more stable.
Th Aug 30 I've simplified and clarified the first problem set. I removed problem 1.1(c)(iii)---I had meant to put k(i + j) not k+(ij). I also added a hint for problem 1.1(b) and clarified what I am asking for in 1.2(c-e).
M Aug 27 I added links to my notes for lectures 1 and 2 in the calendar section at the bottom of the course website. The lecture 1 notes are 10 typed-up pages. I haven't had time to type up the second lecture's notes, so I just scanned in my handwritten notes from the lecture. I wanted to put these here because some of what I covered in lecture, notably how to represent the measurement process classically using pbits and Bayes' rule, is not discussed in any of the reference material for this course.
Th Aug 23 I added Brad's office hours and removed the defunct links to the first problem set to remove any confusion. The link will appear once the set is available. In addition to recommending Chapter 1 of Nielsen & Chuang as a supplement to the first couple of lectures, I added a link to the first in a series of lecture notes by Dave Bacon that covers some of the same material I covered in class. In lecture, I went into much greater detail about Bayes' Rule and pbit measurements, and I plan to post lecture notes on that soon.
W Aug 1 Course credit info (3) and TA info (Brad Chase) has now been added below.
M Apr 30 The course website is under development. If you have questions about the course, please send me e-mail and I'll do my best to answer. In the meanwhile, here is an advertisement for the course.

Course description

This course surveys four major areas of quantum information: algorithms, error correction, communication, and cryptography. Students taking this course will learn how quantum computers can solve problems and crack cryptosystems beyond the reach of classical computers, how noise and decoherence afflicting quantum systems can be reversed with better quantum "software" rather than better quantum hardware, how quantum data can be super-compressed and teleported from one place to another, and how secrets can be protected by the laws of quantum physics rather than the assumed computational difficulty of certain mathematical problems. Linear algebra preparation at the level of Math 314 or Math 321 is required. Prior knowledge of quantum theory is not necessary. Emphasis will be on developing understanding through examples and problem solving. Students taking this course for graduate credit will be expected to solve additional problems and create a Wikipedia article on a quantum information subdiscipline to be presented in class.

General course information

Course Credits: 3

Instructor

Dr. Andrew Landahl (alandahl@unm.edu)
Room 26, Physics and Astronomy
(505) 277-1287

Teaching Assistant

Brad Chase
(bchase@unm.edu)
Room 30, Physics and Astronomy
Phone (505) 277-9153

Class schedule

Physics 452/581: T,Th 11-12:15, P&A 184
Instructor Office Hrs.: M,W 11-12, P&A 26

TA Office Hrs.: W, 2-3

Required Item

Quantum Computation and Quantum Information, Nielsen & Chuang

Optional Items

Lectures on Quantum Computation, Preskill Classical and Quantum Computation, Kitaev, Shen, & Vyali Quantum Theory: Concepts and Methods, Peres Principles of Quantum Computation and Information, Beneti, Casati, & Strini

Prerequisites and corequisites

Prerequisite: Linear algebra at the level of Math 314 or Math 321.

Grading

Undergraduates: Problem sets (100%), Wikipedia article (10%), In-class presentation (10%). (Hence, article & presentation are extra credit.)
Graduate students: Problem sets (80%), Wikipedia article (10%), In-class presentation (10%).
Extra Credit: 5% max total from problem sets

Problem sets

Handed out Tuesdays, due the following Tuesday by 5 p.m. If not turned in during class, use hand-in box labeled "Landahl 452" in Physics and Astronomy main office. Graduate students must do additional in-depth problems on some assignments. Lowest problem set grade dropped; late problem sets not accepted. Each student will be issued a unique "Introduction to Quantum Information (IQI)" number. Keep your IQI number private! You may sign all work by IQI number if you so desire. Homework will be returned in class. Collaboration is fine, indeed encouraged, but you must put significant effort into problems before collaboration and you must write up solutions in your own words. Address all grading issues first with the TA and then with me if they are unresolved.

Wikipedia article and presentation

Graduate students enrolling in the course for credit must create or substantially contribute to a Wikipedia article on a subdiscipline of quantum information. Additionally, a multimedia in-class presentation on the article must be given. Undergraduate students may also undertake this assignment for extra credit.

Lecture notes

I will be posting regular lecture notes to this website. They will be organized somewhat differently than the textbook we are using and may not go into as much depth as the textbook as this is an undergraduate survey course. When possible, I will list on this website which sections in Nielsen & Chuang (NC) a given week's lecture material corresponds to. The optional books and online resources listed above delve more deeply into some of the subjects covered in the required textbook.

Accessibility

Students with special needs should coordinate through Accessibility Services in Mesa Vista Hall (277-3506).

Exam schedule

There are no exams for this course. (Woo hoo!)



Syllabus (tentative)

Mathematics of quantum information

Vectors: Dirac notation, outer product, inner product (NC 2.1)
Matrices: Unitary, Hermetian, Pauli, rotation, positive, polar decomposition (NC 2.1)
Matrix operations: Tensor product, trace, norm (NC 2.1)
Gates: AND, OR, NOT, NAND, NOR, XOR, circuits (NC 3.1.2, 3.2.5)
Axioms of quantum mechanics (NC 2.2)

Quantum algorithms

Quantum gates, circuits, universality (NC 4.2, 4.4, 4.5)
Quantum simulation (NC 4.7, 6.2)
Fourier-transform-based algorithms (Simon, Shor, DJ, Order-finding, HSP) (NC 5)
Amplitude-amplification-based algorithms (unordered search, mean, median) (NC 6.1)
Quantum-walk-based algorithms (Welded trees, element distinctness, spatial search, NAND trees)
Adversary, polynomial lower bound methods (NC 6.7)
Complexity classes: BQP, QMA (NC 4.5.5)

Quantum error correction

Density matrix, quantum operation, POVM, fidelity (NC 2.4, 8.2, 8.3, 2.2.6, 9)
Bit-flip, phase-flip, Shor codes (NC 10.1, 10.2)
Quantum error correction criteria (NC 10.3)
Classical linear codes, CSS codes (NC 10.4)
Stabilizer, binary-vector, GF(4) formalisms (NC 10.5)
Five-qubit code, toric code, Steane code
Hamming, Singleton, Gilbert-Varshamov, no-cloning bounds (NC 10.4
Subsystem, entanglement-assisted codes
Fault tolerant quantum computing (NC 10.6)
Topological quantum computing

Quantum communication

Teleportation, superdense coding, no-cloning (NC 1.3.7, 2.3, 1.3.5, box 12.1)
Schumacher compression, quantum LZ compression (NC 11, 12.2)
Channel capacities (NC 12.1, 12.3, 12.4,
Quantum state redisribution, Mother-Father protocol
Entanglement measures, interconversion, distillation protocols (NC 12.5)
Fisher information, Heisenberg uncertainty

Quantum cryptography

Key distribution (NC 12.6)
Secret sharing
Digital signatures
Coin tossing, bit commitment
Data hiding



Lectures and Problem sets

Tu Aug 21 Course overview; bits and gates; pbits and pgates (Landahl 1; NC 1.1; Bacon 1.II; Preskill Ch. 1)
Th Aug 23 Pbit measurement: Bayes rule; sqrt(NOT) by beamsplitters; complex numbers; qubits and (qu)gates (Landahl 2;NC 1.2, 1.3; Bacon 1.III)
Tu Aug 28 Gate unitarity, Born rule, Dirac notation (Landahl 3; NC 2.1, 2.2; Bacon 1.III, Bacon 2)
Problem Set 1
Solution Set 1
Th Aug 30 Dirac notation examples, linear algebra, spin as a physical qubit (Landahl 4; NC 2.1, 2.2; Bacon 2, 3.I; Preskill 2.2)
Tu Sep 4 Bloch sphere, Deutsch's Algorithm (Landahl 5; NC 1.2, 1.3, 4.2, 1.4.3; Bacon 2, 3.II.A; Preskill 6.3)
Problem Set 2
Solution Set 2
Th Sep 6 Examples of query complexity problems (Landahl 6; NC 1.4.3, 1.4.4, 6.1, 5.4.3; Bacon 3.II.A, 6.II, 7, 8)
Tu Sep 11 Simon's problem; Big-O notation; query models & kinds of query algorithms (Landahl 7) Problem Set 3
Solution Set 3
Th Sep 13 Query complexity results; Deutsch's algorithm walkthrough (Landahl 8)
Tu Sep 18 Analog vs. Digital computation; linear scaling of gate errors; universal gate bases (Landahl 9)
W Sep 19 Repetition code; reversible encoding; no-cloning theorem; observables (Landahl 10)
Th Sep 20 Quantum compiling: the Solovay-Kitaev Theorem and the Solovay-Kitaev algorithm (Landahl 11; Dawson-Nielsen)
M Sep 24 Observables for error correction; circuits for quantum bit flip code and phase flip code (Landahl 12)
Tu Sep 25 Gottesman-Knill Theorem; Magic states; Grover's algorithm: algebraic analysis (Landahl 13)
Problem Set 4
Solution Set 4
Th Sep 27 Grover's algorithm: geometric analysis; reduction of factoring to order-finding (Landahl 14)
Tu Oct 2 Order-finding as a query problem; reduction of order-finding to the quantum Fourier transform (QFT), modular exponentiation, and the continued-fraction algorithm; discrete and quantum Fourier transform; product representation and quantum circuit for QFT (Landahl 15)
Th Oct 4 Continuous fraction algorithm; modular exponentiation; factoring overview; quantum algorithms not (obviously) based on Grover/QFT: ordered search, element distinctness, NAND trees, welded binary trees (Landahl 16)
Tu Oct 9 Shor code; Schmidt decomposition (Landahl 17)
Problem Set 5
Solution Set 5
Th Oct 11 UNM Holiday - Fall Break  
Tu Oct 16 Class cancelled: made up in Lecture 10  
Th Oct 18 Class cancelled: made up in Lecture 12  
Tu Oct 23 Class cancelled  
Th Oct 25 Schmidt decomposition; density matrices (Landahl 18)
Tu Oct 30 Quantum operations (Landahl 19)
Th Nov 1 Examples of quantum channels (Landahl 20)
Tu Nov 6 POVMs; distance measures for quantum states (Landahl 21)
Th Nov 8 Unambiguous state discrimination; distance measures for quantum states; quantum error correcting criteria (Landahl 22)
Tu Nov 13 Quantum State Discrimination; QEC Criteria; degenerate vs. nondegenerate codes (Landahl 23)
Problem Set 6
Solution Set 6
Th Nov 15 Located errors; error detection; QEC critera proof; linearity of QEC; bounds on QEC parameters (Landahl 24)
Tu Nov 20 Pauli group; stabilizer coding theory (Landahl 25)
Th Nov 22 UNM Holiday - Thanksgiving  
Tu Nov 27 Stabilizer codes: syndrome & recovery; examples of stabilizer codes (Landahl 26)
Th Nov 29 Quantum Key Distribution (Landahl 27)
Tu Dec 4 Quantum Communication (Landahl 28)
Th Dec 6 WIKIPEDIA PROJECT PRESENTATIONS  
Tu Dec 11 WIKIPEDIA PROJECT PRESENTATIONS 12:30-2:30 p.m.  
Th Dec 13 No class - Final exam week  

Material on this site is subject to revision. Last updated: Nov. 12, 2007.