Cornell

Physics / Computer Science

Physics 4481-7681 / CS 4812: Quantum Information Processing

Fall 2012
Tue/Thu 1:25-2:40 PM, Location: PSB 120
3 credits, S/U Optional

Note: This is the course website from Fall 2012.
The new website is here: Spring '14

Professor: Paul Ginsparg (452 Phys.Sci.Bldg, ginsparg@cornell.edu)
Office hours: Wed 3-4 PM (or by appointment)
Course website: http://people.ccmr.cornell.edu/~ginsparg/P4481-P7681-CS4812/ (this page)

Hardware that exploits quantum phenomena can dramatically alter the nature of computation. Though constructing a working quantum computer is a formidable technological challenge, there has been much recent experimental progress. In addition, the theory of quantum computation is of interest in itself, offering strikingly different perspectives on the nature of computation and information, as well as providing novel insights into the conceptual puzzles posed by the quantum theory.
The course is intended both for physicists, unfamiliar with computational complexity theory or cryptography, and also for computer scientists and mathematicians, unfamiliar with quantum mechanics.
The prerequisites are familiarity (and comfort) with finite dimensional vector spaces over the complex numbers, some standard group theory, and ability to count in binary. (If this seems too vague, please peruse a copy of the course text in the library to assess its accessibility. Notes on which the text was based are still available here.)

Topics:

  1. A quick but honest introduction to quantum mechanics for computer scientists and mathematicians, simplified by focus on the specific set of relevant applications (measurement, not dynamics)
  2. Some simple, if artificial, quantum algorithms that are surprisingly more efficient than their classical counterparts
  3. Shor's super-efficient period finding (factoring) algorithm and its threat to cryptographic security
  4. Grover's efficient search algorithm
  5. The miracle of quantum error correction
  6. Quantum "weirdness": applications of Bell's theorem
  7. Other forms of quantum information processing and conundra: quantum cryptography; superdense coding; teleportation

Course Text: N.D. Mermin, Quantum Computer Science: An Introduction, Cambridge Univ Press (2007)
Supplemented by Quantum Computation and Quantum Information (Nielsen and Chuang), and other on-line resources

The most recent previous syllabus is here: Spring 2011

Lecture 1 (Thu 23 Aug 12)

Began with historical overview, see, e.g., chapter 1 of Preskill notes, see also The Feynman Lectures on Computation (Hey and Allen).
Covered roughly pp 1-7 (1.1-1.2) of course text: intro, Cbits vs Qbits
(For background on vector spaces and notation, see Appendix A of course text.)
Some other popular expositions of reversible and quantum computing.
A couple other popular refs mentioned (access from within Cornell network): The Fundamental Physical Limits of Computation (Bennett and Landauer, SciAm Jul 1985); Demons, Engines and the Second Law (Bennett, SciAm Nov 1987)

Lecture 2 (Tue 28 Aug 12)

Covered pp 8-18 (1.3-1.5) of course text: reversible operations (inversion, swap, Cnot), number op, Hadamard, states of Qbits, entanglement.

Problem Set 1 (due in class Thu 6 Sep 2012)

Lecture 3 (Thu 30 Aug 12)

Covered pp 19-27 (1.6-1.8) of the course text: Reversible operations on Qbits, circuit diagrams, measurement gates, and the Born rule. (See also appendices B,C of course text.)

Lecture 4 (Tue 4 Sep 12)

Covered pp 27-32 (1.9-1.10) of the course text (finish chapt 1): Generalized Born rule, measurement gates and state preparation, including digression on parts of Appendix B on U(2)=SU(2)xU(1) and SO(3)=SU(2)/Z2.

Lecture 5 (Thu 6 Sep 12)

Covered 32-35 (1.11-1.12) of the course text (finish chapt 1): constructing arbitrary 1- and 2-Qbit states.
Start functions, pp 36-39 (2.1) of course text

Lecture 6 (Tue 11 Sep 12)

Continued functions, then Deutch's problem, pp 39-46 (2.1-2.2), started Bernstein-Vazirani problem, pp 51-54 (2.4).
Overall progression to come: Deutsch -> Deutsch-Jozsa -> Bernstein-Vazirani -> Simon -> Shor, experimental realizations.

Problem Set 2 (due in class Thu 20 Sep 2012)

Lecture 7 (Thu 13 Sep 12)

Finish Bernstein-Vazirani problem, pp 51-54 (2.4), start Simon's problem, pp 54-57 (2.5)

Lecture 8 (Tue 18 Sep 12)

Finish Simon's problem (p. 57 and appendix G) [now halfway through standard algorithms], and quantum Toffoli gates (pp 58-60 (2.6), and latter part of appendix B)

Lecture 9 (Thu 20 Sep 12)

More from appendix B (pp 170-172) on relation between SU(2) and SO(3), why additional Qbits don't mess things up, pp 46-50 (2.3), appendix D on the "spooky" Hardy State (pp 175-178). (See also "Shut up and calculate")
Started chpt. 3 (3.1-3.2), period finding and "Fermat's Little theorem"

Lecture 10 (Tue 25 Sep 12)

Continue chapt 3, some group theory, and RSA (3.2-3.3, and appendix I)

Problem Set 3 (due in class Thu 4 Oct, or via alternate means by 11 Oct)

Lecture 11 (Thu 27 Sep 12)

Finish RSA, Euclid's algorithm (see also cs 2800 notes or pp 39-60 here), some comments on RSA numbers, start Quantum period finding (3.3-3.4, pp. 67-70), and appendix J

Lecture 12 (Tue 2 Oct 12)

Period finding and factoring (3.10, p.87), Quantum period finding and the quantum Fourier transform (3.5, pp.71-72, plus p.80)

Lecture 13 (Thu 4 Oct 12)

Implement the fourier transform (3.5-3.6, p.73-79), eliminate 2-Qbit gates, relation to diffraction grating. How to factor N=15.

Fall Break
9 Oct 2012: coincidental news on Nobel Prize for Quantum info to Wineland and Haroche (plus Monroe/Wineland (2008) SciAm article on quantum computing)

No Lecture (Thu 11 Oct 12)

begin to think about articles for final project

Problem Set 4 (due in class Thu 25 Oct)

Lecture 14 (Tue 16 Oct 12)

Back to finding the period (3.7, pp. 80-83), using continued fractions plus examples (appendix K, 197-200, plus some recreational mathematics), Fermat primes, more recreation

Lecture 15 (Thu 18 Oct 12)

Calculating the periodic function (3.7, 83-84), unimportance of small phase errors (3.8, 84-86).
Current quantum factoring record is 143.
Started chpt 4, pp. 88-91 (4.1-4.2, search and the Grover iteration)

Lecture 16 (Tue 23 Oct 12)

Continue chpt 4, pp. 88-91 (4.2-4.5, search and the Grover iteration); see also pedagogical reviews: Grover's and Lavor et al.'s.
The optimality of Grover's algorithm is shown here.

Lecture 17 (Thu 25 Oct 12)

Finish discussion of (n-1)-fold control Z operator (figs 4.5-4.7).
Now finished the basic basic quantum algorithms.
comment on Grover integration.
Comments on Quantum cakes and Bell inequalities.
Start quantum error correction, simplified example of 3 Qbit single bit flip detection (5.1-5.2, pp 99-109)

Lecture 18 (Tue 30 Oct 12)

Continue error correction, (5.3-5.4, pp.107-115), physics of error generation, measuring operators
Surface code review mentioned in class

Problem Set 5 (due in class Thu 8 Nov)

Lecture 19 (Thu 1 Nov 12)

Continue quantum error correction (5.4-5.8): Diagnosing error syndromes (pp 115-117), 5-qbit codes (pp 117-119)

Mentioned historical articles (see review ('97)): 9-Qbit: Shor ('95), Shor et al. ('95), 7-Qbit: Steane ('96), 5-Qbit: LANL ('96), IBM ('96)

Lecture 20 (Tue 6 Nov 12)

Note that error correcting operator algebras can also be manipulated using matlab, e.g., this sample code.
5.6-5.7: 7 Qbit code and operations on 7-Qbit codewords (pp. 119-127)
Start discussion of superconducting qubits (note also .1 ms coherence time and 98% fidelity cNOT) and surface codes

Lecture 21 (Thu 8 Nov 12)

Mentioned controlled SWAP (Fredkin) gate, controlled Grover,
6.1: Bell states (pp 136-137), surface codes.
For next time, briefly discussed entanglement based quantum communication over 144 km optical free-space link: quant-ph/0607182 (2006), 0902.2015 (2009), and even bigger: 2008 Quantum channel between Earth and Space (2 x 1485km, and contemporary news items: newscientist, arxivblog, "boffins bounce photons")

Prob Set 5 due (with auto extension til Tues)

Lecture 22 (Tue 13 Nov 12)

Quantum Cryptography (6.2), begin GHZ (6.5)

Re quantum key distribution, mentioned Problem Set 6 (due in class Thu 29 Nov)

Lecture 23 (Thu 15 Nov 12)

finish GHZ (6.5), plus game theoretic version, teleportation (6.5)

Re teleportation news Apr 2011 (plus news articles: forbes, UNSW: "Quantum teleporter breakthrough")

Lecture 24 (Tue 20 Nov 12)

finish teleportation of entangled states (6.5) (plus some comments on Quantum teleportation between remote atomic-ensemble quantum memories), bit commitment (6.3), plus some comments on classical zero knowledge proofs (examples of graph coloring and Hamiltonian circuits / graph isomorphism), and some commments on quantum tomography (see notes) for updated problem 7 on prob set 6.

Lecture 25 (Tue 27 Nov 12)

Quantum dense coding (6.4), physical realization of cNOT (App H), continue notes on quantum tomography, start complexity zoo

Lecture 26 (Thu 29 Nov 12)

Complexity Zoo: Some parting comments on P, NP, et al. and BQP et al., P vs. NP, and 3-SAT (see also Preskill notes chpt 6, pp. 5-10, 22-24, 26-28),
plus a relevant rant (3 May '11) about popular complexophobia.

Note: Article Suggestions for Final Project
Recall diagrammatic review of first part of course
See also "Quantum Algorithm Zoo": compendium of quantum algorithms