|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.|
|Advisory: A prior course in quantum computing such as CS 83A.|
|2. Course Objectives - |
|The student will be able to: |
- Identify a matrix as being positive and/or self-adjoint and/or neither, and compute its eigenvalues and eigenvectors.
- Describe what it means for an algorithm to have polynomial growth, and explain how it can be made equivalent to a logic circuit.
- 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.
- 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.
- 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.
- 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.
- Model the environmental noise of a quantum computing element in terms of super operators and/or Bloch sphere representations.
- Define an oracle for a quantum search algorithm and compare its performance relative to a classical search algorithm.
- Analyze, through a computational estimate, the space requirements of a quantum circuit that emulates a reversible gate logic classical circuit.
- 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 - |
- 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.
- 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.
- 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.
- 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) - |
- Mathematical Tools of Classical and Quantum Information
- Review of real and complex vector spaces
- 2-D Hilbert space
- Hermitian and Positive operators
- Polar and singular-value decomposition
- Eigenvectors and eigenvalues
- Adjoint operators
- Tensor product spaces
- Classical Computation Complexity
- Big-O, Omega and Theta time complexity
- Polynomial growth
- Exponential and logarithmic growth
- Turing Machines and the halting problem
- Reduction of algorithms to circuits
- Traditional Quantum Theory and 2-D Quantum Computing Review
- Review of traditional quantum mechanics axioms
- Spin-1/2 Hilbert Space and Bloch sphere representation
- Qubits and logic gates
- Unitary evolution of qubits
- One- and Two-Qubit circuits
- Separable and mixed bipartite states
- Quantum Mechanics of Non-Orthogonal Measurements
- Mixed states vs. pure states
- The general measurement operator formulation of quantum mechanics
- Positive operator valued measures (POVMs)
- Unitary time evolution of states
- Convexity and distinct realizations of density operators
- Tensor Purifications 1
- Neumark construction
- The Partial Trace
- Neumark-based tensor purification
- Easy tensor purification
- Tensor Purifications 2
- Schmidt representation and the Schmidt number
- The GHJW Theorem
- Using GHJW in easy-tensor purifications
- Kraus representations of superoperators
- The Environment and Quantum Noise Models
- Depolarizing channel
- Phase-damping channel
- Amplitude-damping channel
- The Master Equation
- Quantum Search Algorithms
- The Oracle
- Geometric visualization
- Grover Iteration
- Saving Space in Irreversible Gate Simulation
- Reversibility of Toffoli gate
- Scratch pad memory growth
- Reversal of circuits
- Performance gain
- Survey of Current Speed-up Advantage of Quantum Algorithms
|5. Repeatability - Moved to header area.|
|6. Methods of Evaluation - |
- Tests and quizzes
- Written assignments which include algorithms, mathematical derivations, logical circuits, and essay questions.
- 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 - |
- Lectures which include mathematical foundations, theoretical motivation and coding implementation of quantum mechanical algorithms.
- Detailed review of assignments which includes model solutions and specific comments on the student submissions.
- 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.
- When course is taught fully on-line:
- 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.
- 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 - |
- Textbook assigned reading averaging 30 pages per week.
- Reading the supplied handouts and modules averaging 10 pages per week.
- Reading on-line resources as directed by instructor though links pertinent to programming.
- Reading library and reference material directed by instructor through course handouts.
- 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. |