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 programming in the course, for obvious reasons. 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.
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 221 will give you most
of what you need. Math 222 and/or 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 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 page. If you can
figure out
more or less what the last diagram on the page is doing, you should be
fine.
Repeating for credit
Since Math 475 is now a topics course, it may be repeated for credit.
If you
have taken Math 415 or 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 5th hour, but moving it is not out of the
question. If you are interested but can't take it 5th hour, please
let me know!
Josh's home
page.
