Foothill CollegeApproved Course Outlines

Physical Sciences, Mathematics & Engineering Division
C S 83BTHEORY OF QUANTUM COMPUTING IISummer 2014
5 hours lecture.5 Units

Total Quarter Learning Hours: 60 (Total of All Lecture, Lecture/Lab, and Lab hours X 12)
 
 Lecture Hours: 5 Lab Hours: Lecture/Lab:
 Note: If Lab hours are specified, see item 10. Lab Content below.

Repeatability -
Statement: Not Repeatable.

Status -
 Course Status: ActiveGrading: Letter Grade with P/NP option
 Degree Status: ApplicableCredit Status: Credit
 Degree or Certificate Requirement: AS Degree
 GE Status: Non-GE

Articulation Office Information -
 Transferability: CSUValidation: 11/7/13

1. Description -
Summarizes key results of computational complexity in both classical and quantum realms, provides a unique quantum mechanical language appropriate for modeling realistically noisy environments, and presents quantum search algorithms. The second in a sequence, it begins by establishing some basic results of classical computing theory in terms of Turing machines and algorithm complexity. The density-operator formulation of quantum mechanics is then developed to provide a mathematical tool for modeling entangled states in noisy quantum channels. The course presents quantum search algorithms, memory-saving techniques and current advances and failures in quantum computing.
Prerequisite: None
Co-requisite: None
Advisory: A prior course in quantum computing such as CS 83A.

2. Course Objectives -
The student will be able to:
  1. Identify a matrix as being positive and/or self-adjoint and/or neither, and compute its eigenvalues and eigenvectors.
  2. Describe what it means for an algorithm to have polynomial growth, and explain how it can be made equivalent to a logic circuit.
  3. Write out the axioms of traditional quantum mechanics as applicable to observables which have orthogonal eigenvectors, and give an example using a spin 1/2-inspired Hilbert space.
  4. Explain why the traditional state-vector formulation of quantum mechanics is not always adequate to describe a non-orthogonal measurement, and list the axioms of the density-matrix formulation of quantum mechanics.
  5. Compare and contrast three different ways to purify an ensemble representation of a density matrix as a higher-dimensional entangled state, and compute its non-unitary (super-operator) evolution based on the evolution of the entangled state.
  6. Define a Schmidt basis for a separable density operator of a tensor product space and present an example which demonstrates its ability to model non-unitary evolution of a density matrix in a lower-dimensional space.
  7. Model the environmental noise of a quantum computing element in terms of super operators and/or Bloch sphere representations.
  8. Define an oracle for a quantum search algorithm and compare its performance relative to a classical search algorithm.
  9. Analyze, through a computational estimate, the space requirements of a quantum circuit that emulates a reversible gate logic classical circuit.
  10. List both the earliest and more recent time-complexity improvements that quantum algorithms have made over certain classical algorithms, and give other examples where there is either no improvement or a decrease in performance.

3. Special Facilities and/or Equipment -
  1. The college will provide access to a networked computer laboratory which can access quantum computer simulators and tools either via the Web or loaded onto lab computers.
  2. The college will provide 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, the college will provide a fully functional and maintained 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.


4. Course Content (Body of knowledge) -
  1. Mathematical Tools of Classical and Quantum Information
    1. Review of real and complex vector spaces
    2. 2-D Hilbert space
    3. Hermitian and Positive operators
    4. Polar and singular-value decomposition
    5. Eigenvectors and eigenvalues
    6. Adjoint operators
    7. Tensor product spaces
  2. Classical Computation Complexity
    1. Big-O, Omega and Theta time complexity
    2. Polynomial growth
    3. Exponential and logarithmic growth
    4. Turing Machines and the halting problem
    5. Circuits
    6. Reduction of algorithms to circuits
  3. Traditional Quantum Theory and 2-D Quantum Computing Review
    1. Review of traditional quantum mechanics axioms
    2. Spin-1/2 Hilbert Space and Bloch sphere representation
    3. Qubits and logic gates
    4. Unitary evolution of qubits
    5. One- and Two-Qubit circuits
    6. Separable and mixed bipartite states
  4. Quantum Mechanics of Non-Orthogonal Measurements
    1. Mixed states vs. pure states
    2. The general measurement operator formulation of quantum mechanics
    3. Positive operator valued measures (POVMs)
    4. Unitary time evolution of states
    5. Convexity and distinct realizations of density operators
  5. Tensor Purifications 1
    1. Neumark construction
    2. The Partial Trace
    3. Neumark-based tensor purification
    4. Easy tensor purification
  6. Tensor Purifications 2
    1. Schmidt representation and the Schmidt number
    2. The GHJW Theorem
    3. Using GHJW in easy-tensor purifications
    4. Superoperators
    5. Kraus representations of superoperators
  7. The Environment and Quantum Noise Models
    1. Depolarizing channel
    2. Phase-damping channel
    3. Amplitude-damping channel
    4. The Master Equation
  8. Quantum Search Algorithms
    1. The Oracle
    2. Geometric visualization
    3. Grover Iteration
    4. Performance
  9. Saving Space in Irreversible Gate Simulation
    1. Reversibility of Toffoli gate
    2. Scratch pad memory growth
    3. Reversal of circuits
    4. Performance gain
  10. Survey of Current Speed-up Advantage of Quantum Algorithms

5. Repeatability - Moved to header area.
 
6. Methods of Evaluation -
  1. Tests and quizzes
  2. Written assignments which include algorithms, mathematical derivations, logical circuits, and essay questions.
  3. Final examination
7. 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


8. Disciplines -
Computer Science
 
9. 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.

 
10. Lab Content -
Not applicable.
 
11. Honors Description - No longer used. Integrated into main description section.
 
12. 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.

13. Need/Justification -
This course is a restricted support course for the AS degree in Computer Science.


Course status: Active
Last updated: 2014-06-19 12:47:37


Foothill CollegeApproved Course Outlines