CS 410/510 Top: Introduction to Quantum Computing

Credit Hours:

4/3

Course Coordinator:

Fang Song

Course Description:

In this course, we will study the basic principles and techniques of quantum computing, and discuss some of the applications. The goal is to equip you with the essential tools to appreciate, further explore and (even better) devote to this exciting research area. Tentative topics include: quantum states and circuits, entanglement, quantum algorithms (e.g., Grover’s search and Shor’s factorization algorithms), quantum complexity theory, quantum error-correcting codes, and applications in cryptography.

Prerequisites:

MTH 261 & CS 350

Goals:

Upon the successful completion of this class, students will be able to:

1. Explain qubits, quantum gates, quantum circuits, and measurement.
2. Derive residual quantum state after measurement.
3. Show how to apply unitary operations on quantum states.
4. Prove correctness of quantum algorithms.
5. Design quantum algorithms, describe quantum circuits and analyze the circuit complexity.
6. Explain quantum Fourier transform, construct quantum Fourier transform circuit.
7. Understand phase estimation, describe the quantum algorithm solving phase estimation.
8. Explain order finding, describe and analyze the quantum order finding algorithm based on phase estimation.
9. Explain reduction from factorization to order finding.
10. Describe the hidden subgroup problem.
11. Understand reflection and rotation, describe Grover's search algorithm and geometric analysis.
12. Apply Grover's algorithm for other problems.
13. Define mixed states, describe teleportation and CHSH game, distinguish pure states vs. mixed states.
14. Understand bit-flip and phase-flip errors, construct simple quantum error correction codes, explain the need and principle of fault-tolerant quantum computing.
15. Define complexity classes concerning quantum computation such as BQP, QMA; know some complete problem for QMA; explain the relations with conventional complexity classes.
16. Explain the threats of quantum computing in crypto: Internet cryptosystems (RSA, Diffie-Hellman) will be broken.
17. Describe quantum key distribution.
18. Read and summarize research papers.

Textbooks:

1. Quantum Computing since Democritus, Scott Aaronson, 2013 (recommended)
2. An Introduction to Quantum Computing; Phillip Kaye, Raymond Lafalmme, and Michele Mosca; 2007 (recommended)
3. Quantum Computer Science: An Introduction, David Mermin, 2007 (recommended)

Major Topics:

• Qubit, Quantum Circuit Model
• Quantum query model, Deutsch and Deutsch-Josza algorithms
• Simon’s problem, Quantum Fourier Transform
• Phase estimation, order finding, quantum factorization algorithm
• Grover’s search and lower bound
• Entanglement, Bell’s inequality
• Quantum information formalism
• Entropy, Holevo’s theorem
• Quantum error correction codes
• BQP, QMA
• Quantum cryptography and Post-quantum crypto