Basic Information

Course Objectives:

To introduce fundamental quantum algorithms and computational techniques—such as the Quantum Fourier Transform, amplitude amplification, and quantum walks—and to understand how they provide speedups over classical algorithms for problems like factoring and search. Further, the course will introduce basic quantum complexity classes and quantum query complexity.

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. Multiple Qubit Gates. CNOT Gate. No-cloning theorem (statement). Swap trick. Simulating the classical gates with Quantum gates. Linear Algebra Review. Universal Quantum Gates.
• Basic Quantum Algorithms
  
  • Algorithms based on Amplitude Amplification:
    Quantum Search Algorithm - The Procedure and Geometric Visualisations. Quantum Counting, Searching an Unstructured Database. Grover Search.
  • 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 Quantum Walk: Algorithms for Element Distinctness Problem, Testing Group Commutativity, Triangle Problem
• Quantum Complexity Classes: Classes BQP and their relationships with other complexity classes (does not requires compelxity course as a pre-requisite).
• Quantum Query Complexity Lower Bounds : The Polynomial Method. Lower Bounds for Element-Distinctness and Collision. The Adversary Method, Reichhardt's Theorem, Span Programs.
• (Optional topics) Quantum Information Theory - Density matrices, state discrimination, tomography. Von Neumann entropy and Holevo's bound. Quantum nonlocal games, interactive proofs, and PCP

Learning Outcomes:

After the course, the student should:

• be able to analyse 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, Quantum query lower bounds

Pre-requisites:

• Automata theory (to understand models of computation)
• Discrete Mathematics, and a bit of probability (to grasp the mathematical proofs, probability calculations and combinatorial structures.)
• Linear algebra (to understand the matrix manipulations, vector spaces and dimension arguments, eigenvalues,

Course Load:

The course is a 12-credit course. This means a total of 12 hours of work per week, including lectures.

Grading parameters :

• Assignments+viva (4x10% = 40%)
• Endsem Exam (30%)
• Lecture Notes (10%)
• Reading & Presentation of a small topic (20%)
• We may adjust the percentages and include a midsem exam if the number of students goes really high.