Math 475

Topics in Discrete Mathematics: Quantum Computing

Instructor: Joshua Holden
Office: G207
Office Phone: 877-8320
Web Page:

single-particle quantum


You've probably heard that quantum computers are someday going to be able to defeat problems that would take "classical" computers longer than the lifetime of the universe to solve.  Quantum computers will be able to factor astoundingly large numbers, break the NSA's best ciphers, simulate incredibly complicated processes from physics, chemistry, and biology, and search gigantic databases.

You've probably also heard that the largest problem yet solved by a quantum computer is factoring 15 = (3)(5).

We'll talk about the theory, the promise, and the current state of quantum computing.  In the process, we'll have to immerse ourselves in a world where the value of a bit can be |0> or |1>, or -|0> or -|1>, or |0>+|1>, or |0>-|1>, or.....

The focus of the class is going to be on what could we compute if we had a quantum computer, why, and how.  It's going to have to start with a lot of why, so the beginning of the class is going to involve mostly just getting used to the idea of "quantum bits" --- part math and part philosophy!  Then we are going to start building small circuits, and eventually, short algorithms.  Most everything is going to be small because (a) it's going to be a long time before we can make more than a few quantum bits at a time, and (b) anything large becomes extremely hard to test or debug without a quantum computer!

There will be no (or very little) programming in the course, unless Rose suddenly gets a quantum computer!  There will be about one problem set a week, and a couple of exams (at least one may be a take-home).  Most of the grade will probably be from the homework.  There may be a short paper and/or presentation.

Qubits can be in a
          superposition of states.


The prerequisites for this class are:

quantum Fourier transform

Repeating for credit

Since Math 475 is a topics course, it may be repeated for credit. If you have taken Math 475 in the past, please let me know so that we can make sure the paperwork is taken care of.

Class Schedule Information from Banner

Note that the class is currently scheduled for 6th hour, but moving it is not out of the question. If you are interested but can't take it 6th hour, please let me know!
Josh's home page.