|1. Description - |
|This course presents the rigorous mathematical tools of quantum information theory and provides students with the ability to understand 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.|
|Advisory: C S 1B, 18 and MATH 1B.|
|2. 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 spin-1/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 single-qubit 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 order-finding problem and prove that it can be reduced to a phase estimation problem.
- Show the steps that reduce the prime-number factorization problem to the order-finding problem, and explain why this enables a QFT to do factorization with improved time complexity, thus breaking RSA encryption.
|3. 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 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) - |
- 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” real-valued functions.
- Real and complex Fourier series
- The Fourier transform
- The convolution theorem
- Probability distribution and density functions
- Basic Quantum Mechanical Results
- The traditional state-vector formulation of quantum mechanics
- Dirac notation
- Superposition of states
- Observables and orthogonal measurements
- Completeness relations
- Unitary transformation of states
- 2-D Hilbert space
- Spin ½ systems
- Survey of laboratory and industry spin-1/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 Stern-Gerlach experiment
- Different 2-D bases for a single-qubit Hilbert space
- Bloch sphere representation of qubits
- Unitary (reversible) evolution of a qubits
- Pauli-matrices and Bloch-sphere interpretation of unitary operators
- Single-qubit logic gates
- Quantum wires, circuit elements and interference
- Theory of Two Qubits
- Bipartite system as a 4-D 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 no-cloning 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
- Two-register 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 Order-Finding
- The order-finding problem
- Euclid's algorithm
- The continued fraction algorithm
- Reduction of order-finding to phase estimation
- QFT and Cryptography-Breaking
- Prime number factorization and RSA encoding
- Shor's reduction of factorization to order finding
- The Shor algorithm
- Breaking RSA cryptography with quantum computers
|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. |