(Spring 2018) CS 410/510 - Intro to Quantum Computing

Schedule (Subject to change)

Week 1

  • April 02 Qubit, unitary operation, measurement
    • Reading: Aaronson Lec9 HTML; Watrous Lec1 PDF
  • April 04 tensor product, quantum circuit model
    • Reading: Watrous Lec2 PDF, Lec3 PDF
    • HW 1 Out [PDF TeX], due April 18, 2018 before class.

Week 2

(Lectures canceled due to PQCrypto 2018. Watch the video lectures and study the lecture notes.)

  • April 9 Reversible computation, quantum query model (Review: qubit and gates)
    • Reading: Watrous Lec7 PDF
    • Watch: USEQIP’12 lecture on Quantum algorithms by John Watrous Youtube Part I (~32:38); USEQIP’11 Intro to QC by Mosca Youtube (~1:45:50)
    • If you want to reinforce the basic quantum formalism, Michael Nielsen’s short video series Quantum Computing for the determined can help.
  • April 11 Deutsch’s algorithm, Deutsch-Josza algorithm
    • Reading: Watrous Lec4 PDF, Lec7 PDF
    • Watch: USEQIP’12 lecture on Quantum algorithms by John Watrous Youtube Part II (~56:30); USEQIP’11 Quantum algorithm by Childs Youtube (~57:35)

Week 3

  • April 16 Deutsch-Josza review, Simon’s algorithm
    • Watrous Lec6 PDF
  • April 18 Simon’s algorithm Cont’d, Phase estimation
    • Watrous Lec8 PDF; Vazirani Lec12 PDF
    • HW 1 due. HW 2 Out [PDF TeX], due May 02 before class.

Week 4

  • April 23 Quantum Fourier Transform, Order finding, Kitaev’s algorithm
    • Watrous Lec9 PDF, Lec10 PDF;
  • April 25 Kitaev’s algorithm Cont’d, factoring, Shor’s algorithm
    • Watrous Lec11 PDF; Vazirani Lec8 PDF
    • Extended reading: Hidden subgroup problem framework Vazirani Lec9 PDF

Week 5

  • April 30 Unstructured search, Grover’s algorithm
    • Reading: Vazirani Lec11 PDF; Watrous Lec12 PDF, Lec13 PDF
  • May 02 Optimalilty of Grover’s algorithm
    • Reading: Vazirani Lec10 PDF; [BBBV97]
    • HW 2 due. HW 3 Out [PDF TeX], due May 16 before class.

Week 6

  • May 7 Grover’s lower bound cont’d, Quantum information theory intro
  • May 9 Teleportation, superdense coding, non-local games
    • Vazirani Lec3 PDF; Watrous Lec4 PDF, Lec20 PDF

Week 7

  • May 14 density operators, mixed states, general quantum operations
    • Watrous Lec14 PDF, Lec15 PDF
  • May 16 POVM, Entropy, Holevo’s theorem
    • Vazirani Lec13 PDF, Lec17 PDF
    • HW 3 extended dealine: Friday May 18 5pm PDT. HW 4 Out [PDF TeX], due May 30 before class.

Week 8

  • May 21 Quantum Error correcting and Fault tolerance
    • Vazirani Lec21 PDF; Watrous Lec16 PDF, Lec17 (CSS codes) PDF
  • May 23 Quantum computational complexity
    • Watrous Lec22 PDF

Week 9

  • May 28 (Memorial day. No class.)
  • May 30 Selected topic
    • HW 4 due.

Week 10

  • June 04 Project presentations
    • Babson & Yang: Topological quantum computing
    • Maness: Ion trap quantum computing
    • Huynh & Kelly: quantum tomography
    • Lu: non-abelian HSP
  • June 06 Project presentations
    • Kresta: Quantum Neural networks
    • Elsamanoudy & Testa: quantum hashing
    • Nation & Sanguinetti: Quantum walks algorithms
    • Persson & Veleta: exponential speedup based on quantum walk

Final project report due: Wednesday, June 13, 11:59pm, any time zone.