GauchoSpace site for students taking this course: https://gauchospace.ucsb.edu/courses/course/view.php?id=7724
Announcements:
Professor
- Wim van Dam
- vandam@cs.____.___
- Harold Frank Hall 2151
WvD's office hours in 2015 Spring:
Monday, 11:00--12:00
Wednesday: 11:00--12:00
Course description
- Introduction to quantum computing with an emphasis on the computer science part of the field
- Topics that will be covered are: elementary quantum mechanics, quantum information, quantum gates and circuits, quantum circuit complexity, teleportation, quantum cryptography, Shor's quantum algorithm for factoring integers and discrete logarithms, Grover's quantum searching algorithm, lower bounds in quantum computation, quantum error correction and fault tolerant quantum computation.
- What to expect?
Prerequisites
- I will not assume that you know much about quantum mechanics or theoretical computer science, but I do assume that you want to learn about both fields. You should be mathematically literate as we are going to do a lot of linear algebra over the complex numbers.
- "Quantum mechanics is actually... unbelievably simple, once you take all the physics out"
Textbook
- No textbook is required for this course.
Final Grade
- 50% Examinations + 50% Final Project
Formalities
- ID: CMPSC 290A - Special Topics: Foundations
- translation: a special topics graduate course in Computer Science and Physics that is open to anyone who is interested and prepared enough
- units: 4
Weekly Schedule
- Monday, 13:00-14:50: Class in PHELP 2510
- Wednesday, 13:00-14:50: Class in PHELP 2510
Topics that will be covered
- course formalities, quantum states, measurements and their bases, Wiesner's 1970 Quantum Money
- unitary transformations, amplitudes vs probabilities, Kochen–Specker theorem
- braket notation, C-valued linear algebra, open question about POVMs
- quantum bits, BB84 quantum cryptography, in-class experiments
- combining systems, tensor products, quantum circuits, black-box problems, Deutsch's Algorithm
- Deutsch-Jozsa algorithm, exact versus probabilistic computation, reversible computing of classical functions, query complexity, 'promised problems'
- Bernstein-Vazirani algorithm, GF(2)-valued linear algebra, decision vs function problems; circuit complexity
- partial measurements, Simon's algorithm, quantum vs classical probabilistic computation, polynomial computational complexity
- public key cryptography, RSA, Bach's algorithm for factoring through period finding
- quantum Fourier transform, Shor's algorithm for period finding,
- Diffie-Hellman key exchange, Shor's algorithm for discrete logarithms, elliptic curve cryptography
- Grover's search algorithm, BBBV lower bound on quantum searching
- Quantum computing versus NP, power of quantum computation
- Quantum adiabatic optimization, quantum adiabatic theorem, continuous time quantum computation
- Strengths and weaknesses of QAO
Algorithms that will be covered (or maybe not)
Algorithms before 1994:
- Deutsch's algorithm: Quantum circuits; black box problems
- Deutsch-Jozsa algorithm: Promised problems; exact vs probabilistic computation
- Bernstein-Vazirani algorithm: Decision vs function problems; quantum vs classical probabilistic computation; polynomial computational complexity
- Simon's algorithm: partial measurements; mod 2 computations; exponential computational complexity
Shor 'n Stuff:
- Shor's period finding algorithm: Fourier mod N transformation; approximate unitary transformations
- Bach's algorithm for factoring integers using period finding: modulo N number theory
- Shor's algorithm for solving discrete logarithms
Quantum Searching and Its Limits:
- Grover's search algorithm and quantum lower bound on searching: lower bound techniques, P^NP vs BQP
Quantum Heuristics:
- Quantum Adiabatic Optimization: Hamiltonians; continuous time algorithms
Other algorithms for which we will not have time:
- (Quantum walk algorithms: Hamiltonians; continuous vs discrete time algorithms)
- (Kedlaya's algorithm for counting points of finite field curves: function field theory in algebraic geometry)
- (Quantum algorithms for number field problems: Pell's equation, Principal Ideal Problem, Unit Group Problem, Class Group problem; number field theory; periodicity over the reals)
- (Quantum Physics Algorithms: approximating topological invariants)