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


  • New! <2017-10-09 Mon> See final reports of your and your peers’ projects on the Project page.
  • New! <2017-10-09 Mon> Added a few scribe notes and link to a note related to Grover’s algorithm. See schedule page.
  • <2017-06-07 Wed> HW4 solusiotns posted on D2L.
  • <2017-05-30 Tue> Solutions to HW3 posted on D2L.
  • <2017-05-08 Mon> Solutions to HW1 and HW2 available on D2L.
  • <2017-05-02 Tue> HW 3 out, due on May 16 before class.
  • <2017-04-25 Tue> Correction to HW2: 2 (c) should be \(\|\tilde F_N - F_N\|\leq \varepsilon\).
  • <2017-04-04 Tue> Grad students please sign up for scirbe here. (PSU account needed for access). See Admin page for a Latex template.
  • <2017-04-04 Tue> HW 1 is out (on Schedule page). TeX source file is provided too as a template for you to typeset your solutions.
  • <2017-03-31 Fri> Room changed to Cramer Hall 449!
  • <2017-03-03 Fri> Schedule updated, course project page ongoing.
  • <2017-02-21 Tue> Resource, Admin, Tentative schedule updated.
  • <2017-01-30 Mon> Course webpage is up and more to come! Please let me know for any questions or concerns.


The law of quantum physics is revolutionizing what feasible computation may look like, and a new paradigm of quantum computing has been emerging. Quantum computers can solve some fundamental problems efficiently, sometimes expoentially faster than what we can on a classical computer. Numerous promising applications are being developed such as in chemistry, machine learning, and especially cryptography (the Internet will be broken by quantum attackers!).

In this course, we will study the basic principles and techniques of quantum computing, and discuss some of the applications. The goal is to equip you with the essential tools to appreciate, further explore and (even better) devote to this exciting research area. Tentative topics include: quantum states and circuits, entanglement, quantum algorithms (e.g., Grover’s search and Shor’s factoring algorithms), quantum complexity theory, quantum error-correcting codes, and applications in cryptography.

  • Prerequisite: maturity in algorithm analysis and mathematics (espeically linear algebra, basic probability thoery and group thoery). Quantum mechanics is helpful, but NOT required. This course will be theory-oriented involving reading and writing lots of mathematical proofs. I strongly recommend you skimming through the first few lectures of these notes by Watrous PDF and by Vazirani link to get a sense what we will be dealing with. If you feel uncertain, please email me to set an appoinment, and I’d be happy to discuss with you.
  • Syllabus: PDF, and also on the administratives page.
  • Instructor: Prof. Fang Song @ FAB 120-07. Email: fsong “AT” pdx.edu.
  • Lectures: Tu/Th 2:00 - 3:50 pm @ FAB 47 Cramer Hall 449.
  • Office hours: Tu/W 4 - 5pm, or by appointment.
  • Course mailing list: s17qc@cs.pdx.edu. Follow this link to subscribe.
  • Text: no required ones. We will primarily follow lecture notes and read research papers. See the resource page for recommended books and other useful materials related to the course.

Fun stuff

“Quantum Computing 101” Video