  
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 densityoperator 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, memorysaving techniques and current advances and failures in quantum computing.


Course Objectives  
 The student will be able to:
 Identify a matrix as being positive and/or selfadjoint 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/2inspired Hilbert space.
 Explain why the traditional statevector formulation of quantum mechanics is not always adequate to describe a nonorthogonal measurement, and list the axioms of the densitymatrix formulation of quantum mechanics.
 Compare and contrast three different ways to purify an ensemble representation of a density matrix as a higherdimensional entangled state, and compute its nonunitary (superoperator) 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 nonunitary evolution of a density matrix in a lowerdimensional 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 timecomplexity 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.

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 oncampus (i.e., facetoface) 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 email accounts and ongoing access to computers with internet capabilities.

Course Content (Body of knowledge)  
  Mathematical Tools of Classical and Quantum Information
 Review of real and complex vector spaces
 2D Hilbert space
 Hermitian and Positive operators
 Polar and singularvalue decomposition
 Eigenvectors and eigenvalues
 Adjoint operators
 Tensor product spaces
 Classical Computation Complexity
 BigO, Omega and Theta time complexity
 Polynomial growth
 Exponential and logarithmic growth
 Turing Machines and the halting problem
 Circuits
 Reduction of algorithms to circuits
 Traditional Quantum Theory and 2D Quantum Computing Review
 Review of traditional quantum mechanics axioms
 Spin1/2 Hilbert Space and Bloch sphere representation
 Qubits and logic gates
 Unitary evolution of qubits
 One and TwoQubit circuits
 Separable and mixed bipartite states
 Quantum Mechanics of NonOrthogonal 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
 Neumarkbased tensor purification
 Easy tensor purification
 Tensor Purifications 2
 Schmidt representation and the Schmidt number
 The GHJW Theorem
 Using GHJW in easytensor purifications
 Superoperators
 Kraus representations of superoperators
 The Environment and Quantum Noise Models
 Depolarizing channel
 Phasedamping channel
 Amplitudedamping channel
 The Master Equation
 Quantum Search Algorithms
 The Oracle
 Geometric visualization
 Grover Iteration
 Performance
 Saving Space in Irreversible Gate Simulation
 Reversibility of Toffoli gate
 Scratch pad memory growth
 Reversal of circuits
 Performance gain
 Survey of Current Speedup Advantage of Quantum Algorithms

Methods of Evaluation  
  Tests and quizzes
 Written assignments which include algorithms, mathematical derivations, logical circuits, and essay questions.
 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  
  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 online 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 online:
 Instructorauthored lecture materials, handouts, syllabus, assignments, tests, and other relevant course material will be delivered through a college hosted course management system or other departmentapproved Internet environment.
 Additional instructional guidelines for this course are listed in the attached addendum of CS department online practices.


Lab Content  
 Not applicable.


Types and/or Examples of Required Reading, Writing and Outside of Class Assignments  
  Reading
 Textbook assigned reading averaging 30 pages per week.
 Reading the supplied handouts and modules averaging 10 pages per week.
 Reading online resources as directed by instructor though links pertinent to programming.
 Reading library and reference material directed by instructor through course handouts.
 Writing
 Writing technical prose documentation that supports and describes the programs that are submitted for grades.
