Quantum algorithms
Semester: Monsoon 2007.
Lectures: Monday and Thursday,
13:30-15:00, A-212 (STCS seminar room).
Instructor: Pranab Sen.
Office hours: Just walk into
A-226 any time.
Introduction
This course is an introduction to quantum algorithms and computation.
It is aimed at research scholars in their second year or upwards.
Quantum computation is the recasting of computer science in a quantum
mechanical framework, using quantum bits instead of classical bits as
the basic unit of information storage. Quantum algorithms can sometimes
improve on the best classical algorithms by making use of quantum
phenomena like interference to quickly get rid of the "bad" computation
paths in an algorithm, thereby enhancing the weights of the "good"
computation paths. After Peter Shor's discovery in 1994 of efficient
quantum algorithms for integer factoring and discrete logarithm,
threatening current "classical" cryptography, the field has grown
explosively and is now one of the most active subfields of both
theoretical computer science and theoretical physics.
Practicalities
Students taking this course are strongly advised to attend a course on quantum information and error correction
being offered concurrently by Naresh Sharma, at
the same venue, same time, Wednesdays and Fridays. The first four
lectures (during the week of August 6) are common to both courses.
During that week, exceptionally, I shall lecture on Monday and
Wednesday, and Naresh will lecture on Thursday and Friday.
Prerequisites
No prior knowledge of quantum physics will be assumed; we shall provide
the background required. Some familiarity with the classical computer
science notions of algorithms and boolean circuits will be helpful. The
main background required is linear algebra, more specifically,
familiarity with abstract notions of vector spaces, linear operators,
Hermitian and unitary operators and the spectral theorem for such
operators. We shall not assume prior knowledge of the tensor product;
instead, we shall learn about it during the course. The most important
prerequisite for this course is the so-called mathematical maturity. We
hope to see a variety of quantum algorithms during the course each
using very different ideas and mathematical techniques, and
students should be able to grasp a variety of mathematical concepts.
Topics
We aim to cover a good fraction of the following topics during the
course:
- Mathematical formlisms of quantum states and quantum operations
- Classical versus quantum computation
- Universal gates for quantum computation
- Quantum Fourier transform based algorithms
- Amplitude amplification based algorithms
- Quantum walk based algorithms
- Knot theory based algorithms
During and after the course, you may wonder why there are still so few
classes of quantum algorithms that are known even after more than ten
years since Shor's breakthrough discovery. We do not have a good answer
to that. Hence, we need
your help in remedying this situation. If this course enthuses you to
delve into current research in quantum computation, and excites you
into working in this or related areas, then ... welcome aboard!
Evaluation
Performance will be judged based on homework assignments and a seminar
at the end of the course. The plan is to have a homework assignment
every few weeks. For the course-end seminar, students will have to pick
a topic not covered in the course, read a couple of research papers
about it, and then give a presentation. A list of suggested topics and
research papers will be put up later.
Homework
- Out: August 27, In: September 10. Covers lectures
6-8. Problems.
- Out: September 10, In: October 1. Covers lectures
9-13. Problems.
Study material
For the initial part of this course, we shall use Quantum
computation and quantum information by Nielsen and Chuang as
the basic textbook.
However, we shall study a lot of recent material on quantum algorithms
which is not covered by the textbook. Also, we may do some standard
topics in a different way as compared to the textbook. We shall provide
links to
appropriate study material to support the individual lectures. Below,
the chapters refer to those in the textbook.
- August 6: Introduction
and motivation for quantum computation and information. Recommended reading: Chapters 1 and
2. Slides.
- August 8: Examples of
quantum algorithms and communication protocols. Recommended reading: Chapters 1 and
2. Slides.
- August 9: Postulates of
quantum mechanics, mathematical formalism. Recommended reading: Chapters 1
and 2, John Watrous's lecture notes,
Naresh's handwritten notes.
- August 10: Superdense
coding, linear algebra background, density matrices, partial trace. Recommended reading: Chapters 1 and
2, John Watrous's lecture notes,
Naresh's handwritten notes.
- August 13: Motivating
density matrices and partial trace, embedding classical computation
into quantum. Lecture
notes.
- August 16: Exponential of
matrices, Trotter formula, generalised Pauli matrices, decomposing a
general unitary operator into products of unitaries with scaled
generalised Pauli matrices as Hamiltonians. Recommended
reading: Chapter 4 for simulating quantum systems. Lecture
notes.
- August 20: Universal
gates for quantum computation. Recommended
reading: Chapter 4 for an alternate universality
construction. Lecture
notes.
- August 23: Deutsch,
Deutsch-Jozsa
and Simon's
problems. Recommended
reading: John Watrous's lecture notes on Deutsch-Jozsa
and Simon's
algorithms. Lecture notes.
- August 27: Definition of
hidden
subgroup problem and characters of finite abelian groups. Recommended reading: Babai's survey
article
on characters of finite abelian groups. Lecture notes.
- August 30: Efficient
quantum algorithm for the abelian hidden subgroup problem using the
quantum Fourier transform over the group. Lecture
notes.
- September 6:
Coppersmith's circuit for the quantum Fourier transform over cyclic
groups of power of two orders, definition of the eigenvalue estimation
problem, using eigenvalue estimation for computing the Fourier
transform over any cyclic group. Recommended
reading: Chapter 5 for Coppersmith's circuit and eigenvalue
estimation, Kitaev's original paper for using
eigenvalue estimation in order to compute the quantum Fourier transform
over any cyclic group. Lecture
notes.
- September 10: Efficient
circuit for eigenvalue estimation, method of continued fractions. Recommended
reading: Chapter 5 for eigenvalue estimation and method of
continued fractions. Lecture
notes.
- September 13: Hidden
subgroup problem in integers. Recommended
reading: Chapter 5 for order finding subroutine of Shor's
algorithm and period finding in integers. Lecture notes.
- September 17: Shor's
algorithms for integer factoring and discrete logarithm. Recommended reading: Chapter 5 for
the two Shor's algorithms, survey article
on Shor's discrete logarithm algorithm. Lecture notes.