Physics / Computer Science |

Tue/Thu 1:25-2:40 PM, Location: Rockefeller 231

3 credits, S/U Optional

Due to sabbatical, the course is next scheduled for Fall 2016 (website here).

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:**

- 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)
- Some simple, if artificial, quantum algorithms that are surprisingly more efficient than their classical counterparts
- Shor's super-efficient period finding (factoring) algorithm and its threat to cryptographic security
- Grover's efficient search algorithm
- The miracle of quantum error correction
- Quantum "weirdness": applications of Bell's theorem
- 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

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)

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)

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")

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

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

why additional Qbits don't mess things up, (2.3, pp 46-50) and start quantum Toffoli gates (2.6, pp 58-60)

Digression on parts of Appendix B (pp 170-172) on U(2)=SU(2)xU(1) and the double cover SO(3)=SU(2)/Z

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

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

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)

Started implementation of the quantum Fourier transform

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)

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.

Started quantum search (Grover, chpt 4)

The optimality of Grover's algorithm is shown here, and implications here

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 N

Finished with discussion of GHZ states (6.5 in text) and how their measurement excludes "local reality"

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)

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)):

started 5-qbit codes (5.5, pp 117-118)

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

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

Covered quantum key distribution (6.2, 137-141), started quantum teleportation (6.5, p.149-150)

Some articles on quantum key distribution:

- quant-ph/0607177: 1 Mbit/sec for 20km
- quantum key distribution over 184km optical fibre (2008), over 144km (2007) and 300km (2010)
- Entanglement based quantum communication over 144 km optical free-space link: quant-ph/0607182 (2006), 0902.2015 (2009)
- 2011 quantum key distribution in Tokyo metropolitan area: 1103.3566,
- 2008 quantum repeater (and news article "Quantum cryptography can go the distance")
- and even bigger: 2008 Quantum channel between Earth and Space (2 x 1485km, and contemporary news items: arxivblog, "boffins bounce photons")

Some past refs re teleportation: news article on "Quantum teleporter breakthrough", and highlight on future quantum networks (re 1211.2892)

And office hour this week moved to Thu during class time, 1:25-2:40 (PSB 452).

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