Math 475
Topics in Discrete Mathematics: Quantum Computing
Instructor: Joshua Holden
Office: G207
Office Phone: 877-8320
E-mail: holden@rose-hulman.edu
Web Page: http://www.rose-hulman.edu/~holden
Description
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.
Requirements
The prerequisites for this class are:
- Some of the theory of logic and computing. Math 275 will
give you the minimum necessary. Math 375 and/or Math/CSSE
474 are also good.
- Some matrix and vector algebra. Math 212 will give you
most of what you need. Math 371 would also be helpful, but
not necessary.
- A little bit about algorithms and circuits. Quantum
algorithms and circuits are small (so far!) so you don't need to
know much. If you've had CSSE 120 and either CSSE 132 or
ECE 130, you'll be fine. If not, talk to me --- there's a
good chance you've picked up enough here and there. Or you
can try reading this
site. If you can figure out more or less what the
"full adder" diagram on page 4 is doing, you should be fine.
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.
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.
