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
|
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!)
|
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)
|
| 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)
|
| 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 16 |
Class cancelled: made up in Lecture 10 |
|
| Th Oct 18 |
Class cancelled: made up in Lecture 12 |
|
| Th Oct 25 |
Schmidt decomposition; density matrices
|
(Landahl 18)
|
| 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 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.