CIS 478/678
Introduction to Quantum Computation
Spring 2011
Monday and Wednesday, 15:45 -- 17:05, 4-206K SciTech
Prof. Howard A. BLAIR
Instructor :
Prof. Howard
A. BLAIR
NOTICES:
Course Objective and Approach
The goal of this course is to equip participants with an exact and
rigorous model of controllable quantum state evolution. The course
will enable participants to evaluate claims made about the
consequences of quantum computing and claims made about the
consequences of
quantum mechanical principles for advancing technology.
Prerequisites
Prerequisites by course: CIS 275 and MAT 296. The following is also
recommended: Multi-variable calculus and/or
fundamentals of linear
algebra; i.e. MAT 397 or MAT 331. (Math background topics beyond
those of MAT 296 and CIS 275 will be
briefly reviewed during the course as they are needed.)
Prerequisites by topic:
- Know how to calculate partial derivatives.
- Know how to express a linear function in terms
of a given basis.
- Be able to sketch the images and inverse
images of simple regular 2-d shapes under linear transformations.
- Be able to accurately sketch
the graphs of differentiable functions that have planar or 3-d spatial
graphs, which includes finding maxima, minima, and inflection points.
These topics will be briefly reviewed during the course
as they are needed.
Topics:
-
A brief history of quantum computing
-
Computational view of ordinary differential equations
-
Hamiltonians
-
Classical and quantum state evolution
-
Qubits and quantum registers
-
Classical and quantum circuits
-
Measurement
-
Superdense coding
-
Classical and quantum dynamical systems
-
Reasoning about state evolution with quantum logic
Bibliography:
-
Nielsen, M.A. & Chuang, I. Quantum Computation and Quantum
Information.
Cambridge University Press, 2000. ISBN 0-521-63503-9 (Paperback).
Required
-
Hirvensalo, Mika. Quantum Computing, 2 ed. Springer-Verlag,
2004. ISBN 3-540-40704-9. Recommended
-
Albert, D.Z. Quantum Mechanics and Experience. Harvard
University Press, 1992. ISBN 0-674-74113-7 (Paperback).
Recommended
Course Outcomes:
This is an analytical and computational course
that uses elementary calculus and linear algebra to model the
phenomena of quantum dynamical systems.
The specific educational outcomes are to be able to:
- Comprehension: Understand the relationship between
classical deterministic, classical probabilistic, and quantum
dynamical systems, and in particular, the role of unitary
transformations.
- Comprehension: Define qubits, quantum registers, quantum
gates
- Comprehension: Know and understand in terms of a precise
model what is meant by the {\em state} of a quantum system
- Comprehension: Know and understand the quantum
teleportation protocol
- Comprehension: Know and understand the superdense
coding protocol
- Comprehension: Know and understand the relationship
between teleportation and superdense coding
- Comprehension: (For graduate students) Know and
understand Shor's factoring algorithm.
- Comprehension: Appreciate the issues involved in the
interpretation of {\em basic} quantum mechanics and quantum logic
- Analytical and Computational: Plot trajectories of ODEs
- Analytical: Calculate the change in state of a quantum
system by applying unitary transformations
- Analytical: Simulate the activity of quantum automata
and circuits
- Analytical: Evaluate the claims made about the
consequences of quantum computing and madeabout the consequences of
quantum mechanical principles for advancing technology.
Outcome Measurement:
The grade will be based on the assignments
(see below in the calendar
of topics), which will be equally weighted, and occasional in-class
quizzes that will have the weight of an assignment. (Quizzes will be
determined as, and if, the need arises.) Assignments will be due in
class one week after the assignment is announced, unless otherwise
specified.
Graduate students will be required to complete an expository paper on
Hirvensalo'presentation of Shor's factoring algorithm.
Calendar of Topics:
Approximately week by week. Assumes 14.5 week semester with 3 weeks
distributed through the semester for review of material already
covered, discussion of programming assignments, and quizzes.
-
Review of basic linear algebra plus eigenvalues and
eigenvectors. Assignment: plot linear images of the (planar) unit
circle and use the geometry of the image to numerically estimate
eigenvalues and eigenvectors. (Approx. 1.0 weeks) [Covered in
former offerings of Chaos and Dynamical Systems.]
-
Ordinary differential equations as programs for control of
moving points and plotting trajectories by Euler, mid-point Euler and
basic Runge-Kutta methods. Assignment: Plot trajectory of a moving
point under a given ODE by the three given methods and compare for
accuracy. (Approx. 1.5 weeks) [Covered in former offerings of
Chaos and Dynamical Systems.]
-
Quantum bits and registers. Algebraic conditions for
decomposability. Assignment: Calculation of the action of quantum
gates on quantum bits, calculation of decompositions of decomposable
states. (Approx. 1.5 weeks)
-
No Cloning Theorem, intermediate observations. Assignment:
Graphically trace the proof of the No Cloning Theorem, Model the
basic Stern-Gerlach experiment with quantum gates (with step-by-step
instructions.) (Approx. 1.5 weeks)
-
Quantum teleportation and superdense coding. Assignment:
Application of Hadamard matrices to concretely tracing the protocols.
(Approx. 1 week)
-
Classical and quantum Turing machines, classical and quantum
cellular automata. Assignment: Simulation of a quantum 3-cell ring
using XOR and using Wolfram's NKS rule. (Approx. 1.5 weeks).
[Classical part covered in former offerings of Chaos and
Dynamical Systems.]}
-
Basics of Boolean circuits, Toffoli gates, reversible
circuits. Assignment: Construction of a classical 3-cell ring as a
classical circuit. (Approx. 1 week) [Covered in former offerings
of Chaos and Dynamical Systems.]
-
Quantum circuits. Assignment: representation of a quantum
3-cell ring as a quantum circuit. (Approx. 1.5 weeks)
-
Propositional quantum logic and correctness conditions for quantum
dynamical systems. Assignment: validate quantum logic axioms and
inference rules. (Approx. 1 week)