Course Program:
The field of quantum computation is based on the usage of the non-classical features of quantum systems to obtain efficient solutions for difficult computational problems. There have been some significant advances in this regard, Shor's polynomial time factorization algorithm (with its important implications for cryptography) being the most notable one. This course is aimed at computer scientists and engineers who need not have had a deep education about quantum physics. We will be focusing on the "software" of quantum computation, and any prerequisite material (mostly, a warmup of linear algebra) will be covered as we go along.
Topics:
1. Deterministic and probabilistic finite automata, zero error and one-sided error. Introduction to quantum states. A QFA that recognizes a nonregular language with one-sided error.
2. Why some simple DFA’s heat up the environment. Why zero-error is unrealistic. The Hadamard gate. Measurement. Bra-ket notation and inner products. Computational and other bases. Algorithms with measurements. Quantum Zeno Effect.
3. The Elitzur-Vaidman bomb. Two qubits. Tensor products. Entanglement. The CNOT operation. The no-cloning theorem. Quantum money.
4. Partial measurement. Change of basis. Tensor products of gates. An attack on quantum money.
5. Quantum key distribution. One-time pads. The BB84 protocol. Superdense coding.
6. Teleportation. Quantum circuits. The Toffoli gate. How to construct a quantum circuit computing “the same thing” as a given classical circuit.
7. Deutsch’s algorithm. The Deutsch-Jozsa algorithm.
8. Reduction of factoring to order finding. Classical algorithms for the greatest common divisor and modular exponentiation.
9. Shor’s order finding algorithm. Quantum Fourier transform: Definition and implementation.
10. What the QFT does do periodic superpositions. The probability that k/r is in lowest terms if k is selected randomly in {0, 1, … r-1}.
11. The continued fractions algorithm. Grover’s algorithm.
12. Grover's algorithm concluded.