Print Version

Effective: Spring 2016

Advisory: Advisory: C S 83B.
Grade Type: Letter Grade, the student may select Pass/No Pass
Not Repeatable.
FHGE: Non-GE Transferable: CSU
5 hours lecture. (60 hours total per quarter)

Student Learning Outcomes -
  • A successful student will be able define the problem classes P and NP, and compare classical vs. quantum mechanical algorithms in this context.
  • A successful student will be able define the stabilizer code, and test whether given error correction codes satisfy certain analytically-defined bounds.
Description -
This course presents classical and quantum information theory as applied to the encoding and error correction of quantum data. The third in a sequence, it begins by presenting quantum entanglement and non-orthogonal measurement. Key results of classical information theory are stated in terms of the complexity classes P and NP, and Shannon entropy is defined and extended to include quantum information. Students receive instruction in different distance measures and bounds for comparing fidelity. Several error correction and stabilizer codes are presented and analyzed.

Course Objectives -
The student will be able to:
  1. Use the mathematical tools of linear algebra, tensor products and probability to calculate and analyze a number of systems that model quantum behavior.
  2. Describe the difference between the density matrix and state-vector formulation of quantum mechanics and demonstrate the strengths of each.
  3. State what it means for a problem to be NP-complete, and explain the primary conjecture of information theory regarding the complexity classes P and NP.
  4. Define information entropy and compute the minimum entropy gained by the environment for each bit of information lost (erased) by a computer.
  5. Define the distance measures “fidelity”, “entanglement fidelity” and “trace” and, given a description of an encoding algorithm, compute the value of each.
  6. Write an algorithm for some basic error correction schemes utilizing “flip” and Shore codes.
  7. Explain the difference between classical linear error-correcting codes and quantum error-correcting codes.
  8. Test whether a given error-correction code satisfies certain bounds defined by an associated inequality.
  9. Write the formal description of a stabilizer code and give three examples of a stabilizer code, stating the strengths and limitations of each.
Special Facilities and/or Equipment -
  1. access to a networked computer laboratory which can access quantum computer simulators and tools either via the Web or loaded onto lab computers.
  2. a website or course management system with an assignment posting component, a forum component. This applies to all sections, including on-campus (i.e., face-to-face) offerings.
  3. When taught via Foothill Global Access on the Internet, course management system through which the instructor and students can interact.
  4. When taught via Foothill Global Access on the Internet, students must have currently existing e-mail accounts and ongoing access to computers with internet capabilities.

Course Content (Body of knowledge) -
  1. Mathematical Tools
    1. 2-D Hilbert space
    2. Hermitian operators
    3. Eigenvectors and eigenvalues
    4. Tensor product spaces
    5. Fundamental results from probability and statistics
  2. Quantum Mechanical Tools
    1. State vector and density matrix formulations of quantum axioms
    2. Orthogonal and non-orthogonal measurements
    3. Positive operator valued measures (POVMs)
    4. Spin-1/2 Hilbert Space and Bloch sphere representation
    5. Purifications survey and Schmidt number
    6. GHJW theorem
    7. Superoperators and their operator sum representations
  3. Complexity Classes P and NP
    1. Decision Problems
    2. Classes P and NP
    3. NP-complete problems
    4. The “P not-equal NP” problem
    5. Examples in number factoring and graph theory
  4. Classical Information Theory
    1. Random variables and probabilities
    2. Shannon entropy
    3. Mutual information
    4. Data compression and code words
    5. Data transmission over noiseless channels
    6. Data transmission over noisy channels
  5. Distance
    1. Trace
    2. Fidelity
    3. Entanglement fidelity
  6. Basic Error Correction Examples
    1. 3-qubit bit flip code
    2. 3- qubit phase flip code
    3. The Shor code
  7. Fundamental Quantum Error Codes
    1. Classical linear codes
    2. CSS Codes
    3. 7-Qubit code
  8. Constraints on Code Parameters
    1. Quantum Hamming bound
    2. No-cloning bound
    3. Quantum Singleton bound
  9. Stabilizer Codes
    1. Formalism
    2. Unitary gates in the stabilizer formalism
    3. Measurement in the stabilizer formalism
    4. 5-qubit code
    5. 3 qubit bit-flip code revisited
    6. 9-qubit Shor code
Methods of Evaluation -
  1. Tests and quizzes
  2. Written assignments which include algorithms, mathematical derivations, logical circuits, and essay questions.
  3. Final examination
Representative Text(s) -
Nielsen, M. and Chuang, I.: Quantum Computation and Quantum Information, Cambridge University Press, 2010.
Kaye, P., Laflamme, R. and Mosca, M.: An Introduction to Quantum Computing, Oxford University Press, 2007.

Disciplines -
Computer Science
Method of Instruction -
  1. Lectures which include mathematical foundations, theoretical motivation and coding implementation of quantum mechanical algorithms.
  2. Detailed review of assignments which includes model solutions and specific comments on the student submissions.
  3. In person or on-line discussion which engages students and instructor in an ongoing dialog pertaining to all aspects of designing, implementing and analyzing programs.
  4. When course is taught fully on-line:
    1. Instructor-authored lecture materials, handouts, syllabus, assignments, tests, and other relevant course material will be delivered through a college hosted course management system or other department-approved Internet environment.
    2. Additional instructional guidelines for this course are listed in the attached addendum of CS department on-line practices.
Lab Content -
Not applicable.
Types and/or Examples of Required Reading, Writing and Outside of Class Assignments -
  1. Reading
    1. Textbook assigned reading averaging 30 pages per week.
    2. Reading the supplied handouts and modules averaging 10 pages per week.
    3. Reading on-line resources as directed by instructor though links pertinent to programming.
    4. Reading library and reference material directed by instructor through course handouts.
  2. Writing
    1. Writing technical prose documentation that supports and describes the programs that are submitted for grades.