Basic Information

Course Objectives:

To read and understand a computer science view towards quantum computing with a stress on quantum algorithms.

Syallbus:

• The Quantum Computing Model
  Introduction. History. Church-Turing Thesis. Quantum vs Probabilistic Algorithms. Qubits, Basic Qubit operations. Single Qubit Gates. X Gate. Matrix formulation. Unitary Property. Reversibility. Mutiple Qubit Gates. CNOT Gate. No-cloning theorem (statement). Swap trick. Simulating the classical gates with Quantum gates. Linear Algebra Review. Universal Quantum Gates.
• Algorithms based on QFT
  Deutsch's Algorithm. Deutsch-Jozsa Algorithm, Simon's Algorithm. Phase Estimation and Quantum Fourier Transform. Eigenvalue estimation, Order Finding, Factoring. Period Finding, Discrete Logarithms, The Hidden Subgroup Problem.
• Algorithms based on Amplitude Amplification
  Quantum Search Algorithm - The Procedure and Geometric Visualizations. Quantum Counting, Searching an Unstructured Database. Optimality of the Search Algorithm.
• Algorithms based on Quantum Walk Algorithms for Element Distinctness Problem, Testing Group Commutativity, Triangle Problem
• Quantum Complexity Theory : Classes BQP and their relationships with other complexity classes.

Learning Outcomes:

After the course, the student should:

• be able to analyze simple quantum algorithms and possibly see abstractions of the kind in various contexts
• Appreciate the speed up from quantum parallelism
• Have enough familiarity to read and understand the research papers in Quantum Algorithms

Pre-requisites:

This is a reading course. This means there will not be lectures by the instructor through the course. The first few will be handled by the instructor to initiate the reading process establishing the motivation and basic ideas etc. Hence the pre-requisites to include the ability to read up yourself on a fresh material and understand. Some soft pre-requisite would include Automata theory course (to have a view towards computability). It will be advisable to have a basic linear algebra background too, but most of what is required will be developed (at a slightly fast pace) in the intial part of the course.

Course Load:

The course is a 4 credit course. This means total of 12 hours of work per week, including meetings. Thus a student is expected to spend about 10 hours on the course. This will be the case for a student with not enough background. For an average student, the course load on average will be about 6-8 hours a week.

Grading parameters :

• Reading & Presentations (30%+5%+5%)
• Midsem Exam (15%)
• Random Short Tests (10%)
• Endsem Exam (30%)
• Participation (5%)