Topics in Mathematics: Quantum Computing
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.
The prerequisites for this class are:
- Some of the theory of logic and computing. Math 275 or 276 will give you the minimum necessary. Math 375 or 374 and/or Math/CSSE 474 are also good.
- Some matrix and vector algebra. Math 212 or 221 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 233, 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.
Class Schedule Information from Banner
(Note that there will be some online synchronous meetings but the time listed on Banner is flexible; if you can’t make class at that time feel free to talk to me about other possibilities.)