Cornell

Physics / Computer Science

Physics 4481-7681 / CS 4812: Quantum Information Processing

Spring 2014
Tue/Thu 1:25-2:40 PM, Location: Rockefeller 231
3 credits, S/U Optional

Note: This is the course website from Spring 2014.
Due to sabbatical, the course is next scheduled for Fall 2016 (website here).

Professor: Paul Ginsparg (452 Phys.Sci.Bldg, ginsparg@cornell.edu)
Office hours: Wed 2-3 PM (or by appointment)
Course website: https://courses.cit.cornell.edu/physics4481-7681_2014sp/ (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), Quantum Computing since Democritus (Aaronson), and other on-line resources

The most recent previous syllabus is here: Fall 2012

Lecture 1 (Thu 23 Jan 14)

Begin 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-4 (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 Jan 14)

Sketched complexity hierarchy (where BQP likely fits in P, NP, NP-hard, NP-complete scenario)
Covered pp 4-16 (1.2-1.4) of course text: reversible operations (inversion, swap, Cnot), Hadamard

Problem Set 1 (due in class Thu 6 Feb 2014)

Lecture 3 (Thu 30 Jan 14)

Discussion of direct (Kronecker) products, 2d rotation group, half-wave plates, Hadamard as reflection about π/8, ...
Covered pp 17-20 (1.5-1.6) states of Qbits, entanglement, reversible operations on Qbits
(See also "Shut up and calculate", not to mention "Shut up and let me think")

Lecture 4 (Tue 4 Feb 14)

Discussed SO(n), SU(n)
Covered pp 21-30 (1.7-1.9) of the course text: circuit diagrams, measurement gates, Born rule, generalized Born rule.

Lecture 5 (Thu 6 Feb 14)

Covered pp. 30-35 (1.10-1.12), measurement gates and state preparation, constructing arbitrary 1- and 2-Qbit states, Cbit vs Qbit summary. Started functions, pp 36-39 (2.1)

Problem Set 2 (due in class Tue 25 Feb 2014)

Lecture 6 (Tue 11 Feb 14)

Mentioned gate universality (see "The Solovay-Kitaev Algorithm" for technical review), "pre-review" of algorithms to come (Deutsch -> Deutsch-Jozsa -> Bernstein-Vazirani -> Simon -> Shor; then Grover); covered 38-46 (2.1-2.2) of text (functions, no-cloning and Deutch's problem)

Lecture 7 (Thu 13 Feb 14)

Mentioned Two Quadrillionth Bit of π is 0, covered pp 50-55: Bernstein-Vazirani problem (2.4), started Simeon's problem (2.5), also Appendix B of course text (pp 168-171)

Cornell Break Tue 18 Feb 14

Lecture 8 (Thu 20 Feb 14)

Finish Simon's problem (2.5 and appendix G) [now halfway through standard algorithms], attempted clarification of the arithmetic formula in class is here,
why additional Qbits don't mess things up, (2.3, pp 46-50) and start quantum Toffoli gates (2.6, pp 58-60)

Lecture 9 (Tue 25 Feb 14)

Began with discussion of this very recent article (Barends et al, "Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing", 20 Feb 2014).
Digression on parts of Appendix B (pp 170-172) on U(2)=SU(2)xU(1) and the double cover SO(3)=SU(2)/Z2, and use of "Clifford group" (the 48 element lift of the 24 symmetry rotations of the cube from SO(3) to SU(2), c.f., last problem on prob set 2) to benchmark single Qbit operations in the above reference. Gave a version of the quantum universality argument underlying the constructions in (2.6) of book (pp. 59-62)

Problem Set 3 (due in class Thu 13 Mar 2014)

Lecture 10 (Thu 27 Feb 14)

Finished (2.6), constructions of Tofolli, covered appendix D on the "spooky" Hardy State (pp 175-178)

Lecture 11 (Tue 4 Mar 14)

Correction of X1/2 = HZ1/2H = eiπ/4(1-iX)/21/2 = i1/2(-iX)1/2,
Some additional comments on 1402.4848 (including some material from appendix H of text),
and pointer to Martinis video (talk at Google LA), some additional comments on quantum circuits vs quantum adiabatics vs classical annealing.
Covered Appendix I, then the number theoretic preliminaries (3.1-3.2, pp 63-65), period finding and Fermat's little theorem

Lecture 12 (Thu 6 Mar 14)

Some comments on 1403.0009 ("Teleportation of entanglement over 143 km"), also mentioned quant-ph/9801041 ("Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems"), and mentioned "What is the probability that 6 Mar is Thursday?"
Continued chapt 3, more number theory, and RSA (3.2-3.3), Euclid's algorithm (appendix J, see also cs 2800 notes or pp 39-60 here), some comments on RSA numbers, start Quantum period finding (3.3, pp. 68-69)

Lecture 13 (Tue 11 Mar 14)

Recap of Fermat's little theorem, "Wilson's Theorem"; then using period finding to break RSA encryption, period finding and factoring, period finding and quantum Fourier transform, 3.3-3.5, 3.10 (pp. 67-72, p.87).
Started implementation of the quantum Fourier transform

Lecture 14 (Thu 13 Mar 14)

Mentioned upcoming physics colloquium (M.Devoret, 17 Mar 2014, "Superconducting Artificial Atoms: The Quest for Unlimited Qubit Coherence"), and related article ("Dynamically protected cat-qubits: a new paradigm for universal quantum computation")

Completed implementation of the quantum Fourier transform (see also 3.5, p.73-75), eliminate 2-Qbit gates (3.6, p.73-79), started finding the period (3.7, 80-81), relation to diffraction grating.

Problem Set 4 (due in class Thu 27 Mar, before the break)

Lecture 15 (Tue 18 Mar 14)

Some comments on qutrits and Toffoli.
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.
Started How to factor N=15.

Lecture 16 (Thu 20 Mar 14)

Finished factoring N=15, another example from appendix K, discussed calculating the modular exponent (3.10, answer to question raised in class was that calculating the remainder is also "cheap"), unimportance of small phases (3.9). Current quantum factoring record is 143
Started quantum search (Grover, chpt 4)

Lecture 17 (Tue 25 Mar 14)

Continue chpt 4, pp. 89-98 (4.2-4.5, search and the Grover iteration), one of four items, generalization to several special, construction of W; see also pedagogical reviews: Grover's and Lavor et al.'s.
The optimality of Grover's algorithm is shown here, and implications here

Lecture 18 (Thu 27 Mar 14)

Some comments on sqrt(N) optimality of Grover, finished discussion of (n-1)-fold control Z operator (figs 4.5-4.7).
Now finished the basic basic quantum algorithms.
More comments on qudits and d-fold Toffoli, and experimental use of qutrit to speed up creation of a GHZ entangled state.
Comments on decision problems, the birthday paradox, and the N1/3 quantum collision algorithm.
Finished with discussion of GHZ states (6.5 in text) and how their measurement excludes "local reality"

Lecture 19 (Tue 8 Apr 14)

finish GHZ (6.5), plus game theoretic version (a ⊕ b ⊕ c = r ∨ s ∨ t, where r,s,t ∈ {000, 011, 101, 110})
also some additional comments on quant-ph/9801041 (nonlinear QM solves NP-complete and #P problems, see also Aaronson, pp. 7-8)
Start quantum error correction, simplified example of 3 Qbit single bit flip detection (5.1-5.2, pp 99-107)

Problem Set 5 (due in class Tue 22 Apr)

Lecture 20 (Thu 10 Apr 14)

Noted corrections to problems 6,7 in Problem Set 5, discussed W and GHZ states, and the 3 Qbit result for LOCC inequivalence (general setup using SVD/Schmidt is here).
Continued quantum error correction, (5.3-5.4, pp.107-117), physics of error generation, measuring operators, diagnosing error syndromes
Mentioned historical articles (see review ('97)): 9-Qbit: Shor ('95), Shor et al. ('95), 7-Qbit: Steane ('96), 5-Qbit: LANL ('96), IBM ('96)
started 5-qbit codes (5.5, pp 117-118)

Lecture 21 (Tue 15 Apr 14)

Discussion of controlled unitaries via controlled SWAP (Fredkin) gate, e.g., controlled Grover Gt
finished 5 Qbit code (5.5)
Mentioned Wason selection task, then discussion of "Quantum cakes" and Bell inequalities (prob 8 of problem set 5)
Noted that error correcting operator algebras can also be manipulated using python or matlab, e.g., this sample code.
(See also Sympy Physics Module, specifically quantum computation).

Lecture 22 (Thu 17 Apr 14)

Some additional comments on sample code
5.6-5.8: 7 Qbit code, operations on 7-Qbit codewords, 7-Qbit encoding circuit (pp. 121-128)

Lecture 23 (Tue 22 Apr 14)

Finished discussion of logical cNOT for 7-Qbit code
Covered quantum key distribution (6.2, 137-141), started quantum teleportation (6.5, p.149-150)
Some articles on quantum key distribution: Problem Set 6 (due in class Tue 6 May)

Lecture 24 (Thu 24 Apr 14)

Final comments on Quantum key distribution (6.2), finished teleportation and teleportation of entangled states (6.5), bit commitment (6.3), plus some comments on classical zero knowledge proofs (examples of graph coloring and Hamiltonian circuits / graph isomorphism),
Some past refs re teleportation: news article on "Quantum teleporter breakthrough", and highlight on future quantum networks (re 1211.2892)

Lecture 25 (Tue 29 Apr 14)

Finished bit commitment (6.3), Quantum dense coding (6.4), then quick overview of Surface codes (covered fig.1 and fig.3 of this review, and pages 5-11; problem 8 covers pages 12-13).

Alternate Lecture (Thu 1 May 14)

Lecture cancelled in favor of third of Susskind Messenger lectures, "Entanglement: the hooks that hold space together", same day at 4:30 in Schwartz Auditorium, Rockefeller Hall.
And office hour this week moved to Thu during class time, 1:25-2:40 (PSB 452).

Lecture 26 (Tue 6 May 14)

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, and the abbreviated Petting Zoo).

Note:: ideas for final project (due by 19 May)
Recall diagrammatic review of first part of course
See also "Quantum Algorithm Zoo": compendium of quantum algorithms