COT6600 Quantum Computing

Credit: 3 units

Offered: Fall semester

Instructors: Dan Marinescu and Pawel Wocjan

Class outline

  • Linear Algebra & Dirac Notation
  • Hilbert Spaces and Linear Operators
  • Eigenvectors and Eigenvalues of Quantum Operators
  • Spectral Decomposition of an Operator
  • Elements of Quantum Mechanics
  • Quantum State Postulate
  • Dynamics Postulate
  • Measurements Postulate
  • Uncertainty Principle
  • Density Operator
  • Pure and Mixed States
  • Entanglement; Monogamy of Entanglement
  • Qubits and their Physical Implementation
  • Quantum Gates and Quantum Circuits
  • One-qubit gates: X, Y, Z, Hadamard, Phase-shift
  • Two-qubit gates: CNOT
  • Three-qubit gates: Fredkin and Toffoli
  • Universality of Quantum Circuits, Solovay-Kitaev Theorem, Clifford Group
  • Quantum Computational Models
  • Introduction to Quantum Algorithms
  • Deutsch Algorithm
  • Deutsch-Jozsa Algorithm
  • Bernstein-Vazirani Algorithm
  • Simon's Algorithm
  • Algorithms with Superpolynomial Speed-up
  • Efficient Quantum Circuits for the Fourier Transform
  • Quantum Phase Estimation Algorithm
  • Shor's Algorithm for Factoring Integers and Determining Discrete Logarithms
  • Algorithms for Hidden Subgroup Problems
  • Algorithms for Hidden Nonlinear Structures
  • Algorithms Based on Amplitude Amplification
  • Grover's quantum search algorithm
  • Amplitude Amplification
  • Quantum Counting
  • Quantum Walks
  • Quantum Computational Complexity Theory & Lower Bounds
  • Quantum Complexity Classes BQP (Bounded Quantum Polynomial Time) and QMA (Quantum Arthur Merlin)
  • Complete Problems for QMA: local Hamiltonian problem, Compatibility of density matrices
  • Polynomial method
  • Adversary methods

References:

  • D. C. Marinescu and G. M. Marinescu, “Approaching Quantum Computing,” Prentice Hall, 2004.
  • M. Nielsen and I. Chuang, “Quantum Computing,”CambridgeUniversity Press, 2000.
  • R.P. Feynman, “Lectures on Computation,” Addison-Wesley, Reading, MA, 1996.
  • N. D. Mermin,“Quantum Computer Science: An Introduction,”CambridgeUniversity Press, 2007.
  • R. Penrose,“The Road to Reality: A Complete Guide to the Laws of the Universe,”Vintage Books, 2007.

Literature:

Many research articles can be accessed through the quant-ph archive maintained by Los Alamos National Laboratory.

  • C. H. Bennett,“Logical Reversibility of Computation,” IBM Journal of Research and Development, 17: 525 - 535, 1973.
  • E.Bernstein and U.Vazirani, “Quantum Complexity Theory,”SIAM Journal of Computing, 26: 1411 - 1473, 1997.
  • D. P. DiVincenzo,“Quantum Computation,”Science, 270: 255 - 261, 1995.
  • D. P. DiVincenzo, “The Physical Implementation of Quantum Computation,” Fortschritte der Physik, 48(9-11): 771 - 783, 2000.
  • R.P. Feynman,“Simulating Physics with Computers,” International Journal of Theoretical Physics, 21: 467 - 488, 1982.
  • L. K. Grover, “A Fast Quantum Algorithm for Database Search,” Proceedings, ACM Symposium on Theory of Computing, ACM Press, NY, 212 - 219, 1996. Also updated version: Preprint, arxiv.org/quanth-ph/9605043, 1996.
  • L.K. Grover,“From Schrödinger's Equation to the Quantum Search Algorithm,” American Journal of Physics, 69(7): 769 - 777, 2001.
  • R. Jozsa, “Entanglement and Quantum Computation,” Geometric Issues in the Foundations of Science. S. Hugget, L. Mason, K.P. Tod, S.T. Tsou, and N. M. J. Woodhouse, Oxford University Press, 1997.Also: Preprint, arxiv.org/quant-ph/9707034 v1,1997.
  • R. Jozsa, “Quantum Factoring, Discrete Logarithms, and the Hidden Subgroup Problem,” Preprint, arxiv.org/quant-ph/0012084 v1, 2000.
  • R. Landauer, “Irreversibility and Heat Generation in the Computing Process,” IBM Journal of Research and Development, 5: 182 - 192, 1961.
  • S. Lloyd, “A Potentially Realizable Quantum Computer,” Science, 261: 1569 - 1571, 1993.
  • S. Lloyd,“Almost any Quantum Logic Gate is Universal,”Physical Review Letters, 75, 346 - 349 1995.
  • J. Preskill,“Lecture Notes for Physics 229: Quantum Information and Computing,” California Institute of Technology,
  • E.Rieffel and W.Polak,“An Introduction to Quantum Computing for Non-Physicists,” ACM Computing Surveys, 32(3): 300 - 335, 2000.
  • P.W.Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,'' SIAM Journal of Computing,” 26: 1484 - 1509, 1997.
  • P.W.Shor, “Introduction to Quantum Algorithms,”Preprint, arxiv.org/quant-ph/0005003, July 2001.
  • P.W.Shor,“Why Haven't More Quantum Algorithms Been Found?” Journal of the ACM, 50(1): 87 - 90, 2003.
  • A.M.Steane, “Quantum Computing,”Reports on Progress in Physics, 61: 117, 1998.Also: Preprint, arxiv.org/quant-ph/97080222 v2, September 1997.

Grading policy:

Homework 35%

Midterm 25%

Final exam 40%