  
Description  
 Mathematical tools of quantum information theory and provides understanding and design elementary quantum circuits and algorithms. The first of a sequence, it develops the quantum mechanical foundation needed to understand how quantum computers can beat ordinary computers in certain problem classes by using quantum entanglement and teleportation under the ideal condition of a noiseless channel. The endpoint of the course is a working knowledge of the quantum Fourier transform and Shor algorithm, which can be used to break RSA encryption, the basis of current Internet security. No prior knowledge of quantum mechanics is required.


Course Objectives  
 The student will be able to:
 Define and solve problems that involve the basic linear algebra and complex arithmetic needed in quantum computing theory.
 Use Fourier theory to write a Fourier sum for a given a periodic function or a Fourier transform for a given general function.
 State the axioms of traditional quantum mechanics in Dirac notation and compute the probabilities associated with a measurement on a spin1/2 atom in a magnetic field.
 Given a classical circuit diagram containing basic logic gates (AND, OR, etc.), compute the outputs given a set of input bits.
 Define a qubit and, given a quantum circuit diagram containing singlequbit logic gates, compute its output given an input qubit.
 Explain the difference between reversible and irreversible gate logic and give examples demonstrating how entangled states can be exploited in order to emulate a classical irreversible circuit using an irreversible quantum circuit.
 Write out a quantum circuit that will perform quantum teleportation of a qubit using entangled states and explain why the same cannot be done using a classical logic or information exchange.
 Explain the difference between the discrete Fourier transform (DFT) and the fast Fourier transform (FFT), and define the quantum Fourier transform (QFT).
 Define the phase estimation problem and give an analytical summary of how a QFT can solve it.
 Define the orderfinding problem and prove that it can be reduced to a phase estimation problem.
 Show the steps that reduce the primenumber factorization problem to the orderfinding problem, and explain why this enables a QFT to do factorization with improved time complexity, thus breaking RSA encryption.

Special Facilities and/or Equipment  
  access to a networked computer laboratory which can access quantum computer simulators and tools either via the Web or loaded onto lab computers.
 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)  
  Linear Algebra and Complex Arithmetic
 Vector spaces, bases, inner products, orthogonality, orthonormality
 Linear transformations, matrices, inverses and the transpose
 Direct sums and direct products
 Eigenvectors and eigenvalues
 Complex arithmetic, the complex plane and conjugation
 Complex vector spaces and unitary operators
 The exponential operator applied to a complex matrix
 Elementary Fourier Theory and Probability
 Trigonometric functions and identities
 Survey and definitions of derivatives and integrals of “well behaved” realvalued functions.
 Real and complex Fourier series
 The Fourier transform
 The convolution theorem
 Probability distribution and density functions
 Basic Quantum Mechanical Results
 The traditional statevector formulation of quantum mechanics
 Dirac notation
 Superposition of states
 Observables and orthogonal measurements
 Completeness relations
 Unitary transformation of states
 2D Hilbert space
 Spin ½ systems
 Survey of laboratory and industry spin1/2 computers
 Classical Computation Theory
 The classical bit
 Logic gates and truth tables
 Universal gates
 Reversible and irreversible circuits
 Fredkin and Toffoli gates
 Emulating irreversibility with reversible logic
 Time complexity of algorithms
 Quantum Computation: A Single Qubit
 The SternGerlach experiment
 Different 2D bases for a singlequbit Hilbert space
 Bloch sphere representation of qubits
 Unitary (reversible) evolution of a qubits
 Paulimatrices and Blochsphere interpretation of unitary operators
 Singlequbit logic gates
 Quantum wires, circuit elements and interference
 Theory of Two Qubits
 Bipartite system as a 4D tensor product space
 Bases, Bell states and quantum entanglement
 Unitary evolution in bipartite system vs. evolution in single qubit system
 Quantum gates from classical irreversible gates
 Quantum gate emulation of irreversible classical gates
 The nocloning theorem
 Two Qubit Circuits and Early Algorithms
 Universal quantum gates
 Quantum teleportation
 Superdense coding
 Deutsch's algorithm
 Time complexity speedup of Deutch's algorithm: theoretical vs. actual
 The Quantum Fourier Transform
 The discrete FT
 The fast Fourier transform (FFT)
 FFT improvement of polynomial multiplication
 Time complexities of FFT and DFT
 The QFT
 Circuit and time complexity for QFT
 QFT and Phase Estimation
 Tworegister implementation of phase estimation of an “ideal phi”
 Relationship between phase estimation and inverse FT
 Phase estimation when phi is not ideal
 Quantum phase estimation algorithm
 QFT and OrderFinding
 The orderfinding problem
 Euclid's algorithm
 The continued fraction algorithm
 Reduction of orderfinding to phase estimation
 QFT and CryptographyBreaking
 Prime number factorization and RSA encoding
 Shor's reduction of factorization to order finding
 The Shor algorithm
 Breaking RSA cryptography with quantum computers

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.
