Quantum Computing Course: Algorithms, Query Model & Limitations | IIT Kanpur
Course Details
| Exam Registration | 2302 |
|---|---|
| Course Status | Ongoing |
| Course Type | Elective |
| Language | English |
| Duration | 12 weeks |
| Categories | Computer Science and Engineering |
| Credit Points | 3 |
| Level | Postgraduate |
| Start Date | 19 Jan 2026 |
| End Date | 10 Apr 2026 |
| Enrollment Ends | 02 Feb 2026 |
| Exam Registration Ends | 20 Feb 2026 |
| Exam Date | 24 Apr 2026 IST |
| NCrF Level | 4.5 — 8.0 |
Quantum Computing: Algorithms and Limitations Through the Query Model
Quantum computing has transitioned from a theoretical curiosity to a tangible frontier in computer science and engineering. With the promise of solving problems intractable for classical computers, it has captured the imagination of researchers and industry alike. This detailed exploration is based on a comprehensive 12-week postgraduate course designed and taught by Prof. Rajat Mittal at IIT Kanpur, which delves deep into the algorithms that define quantum advantage and the fundamental limitations that bound it, primarily through the powerful lens of the query model.
Course Overview and Instructor Profile
This advanced course is structured to provide a rigorous, computer science-focused perspective on quantum computation. It is led by Prof. Rajat Mittal, an associate professor at IIT Kanpur with a distinguished background. After completing his PhD from Rutgers University, Prof. Mittal spent three years as a postdoctoral fellow at the prestigious Institute for Quantum Computing in Waterloo, Canada. His research interests lie at the intersection of quantum and classical computing, where he employs tools like linear/semidefinite programming and Fourier analysis to explore the advantages and inherent limits of quantum machines. His dedication to pedagogy is evidenced by awards like the “1989 Batch faculty teaching award for innovation in teaching 2021” and the “Excellence in teaching award 2019, IIT Kanpur”.
Who Should Take This Course?
The course is meticulously designed for postgraduate students and professionals aiming to build a strong theoretical foundation in quantum algorithms.
- Intended Audience: Computer scientists and mathematicians seeking to understand the fundamentals and advanced concepts of quantum algorithms.
- Prerequisites: A solid grasp of Linear Algebra and Probability is essential to follow the mathematical formalism.
- Industry Support: The curriculum is highly relevant for:
- Quantum Technology Companies & Startups
- Government & Research Labs (e.g., DRDO, ISRO)
- Advanced Software Consulting Firms
Detailed 12-Week Course Layout
The course progresses from foundational concepts to advanced topics in quantum complexity theory.
| Week | Topics Covered |
|---|---|
| Week 1 | What is quantum computing? Quantum weirdness: Mach-Zehnder interferometer. |
| Week 2 | Linear algebraic formulation of states: deterministic, randomized and quantum, qubits, composite systems. |
| Week 3 | Operations in quantum computing, basic gates and circuits, Mach-Zehnder in terms of quantum operations. |
| Week 4 | Semidefinite matrices, projectors, measurements, principle of deferred measurement. |
| Week 5 | Classical vs. quantum circuits, Deutsch (from Mach-Zehnder) and Deutsch-Jozsa algorithms, swap circuit. |
| Week 6 | Randomized computation with examples, setting the stage for quantum speedups. |
| Week 7 | Simon’s algorithm, Quantum Fourier transform, and its groundbreaking applications: phase estimation and Shor’s factoring algorithm. |
| Week 8 | Grover’s search algorithm, amplitude amplification and its variants. |
| Week 9 | Random walks and discrete-time quantum walks. |
| Week 10 | Query Model: Classical and quantum, approximate degree, optimality of Grover search. |
| Week 11 | Total functions: Understanding why there is at most a polynomial separation between deterministic and quantum query complexity. |
| Week 12 | Super-quadratic separation: Cheatsheet model, partial functions, Aaronson-Ambainis conjecture, and the Forrelation problem. |
Core Focus: Algorithms and the Query Model
The heart of the course lies in its dual focus: understanding the revolutionary algorithms that promise quantum advantage and the theoretical models that define its limits.
Key Quantum Algorithms Covered
- Shor’s Algorithm: The algorithm that sparked widespread interest in quantum computing by showing an efficient method for integer factorization, threatening classical cryptographic systems like RSA.
- Grover’s Algorithm: Provides a quadratic speedup for unstructured search problems, a fundamental primitive with broad applications.
- Quantum Fourier Transform (QFT): The quantum analogue of the discrete Fourier transform, serving as the crucial subroutine in Shor’s algorithm and many others.
- Amplitude Amplification: A generalization of Grover's search that boosts the probability of a desired outcome.
Understanding Limits: The Power of the Query Model
A significant portion of the course is dedicated to the query model (or black-box model), a powerful abstraction in computational complexity. This model allows computer scientists to:
- Prove lower bounds on the number of queries (or calls to an oracle) a quantum algorithm must make to solve a problem.
- Formally establish the optimality of algorithms like Grover’s search.
- Explore the maximum possible separation between quantum and classical computing power for different problem types (e.g., total vs. partial functions).
- Investigate modern conjectures and results, such as the Aaronson-Ambainis conjecture and the Forrelation problem, which demonstrate super-quadratic quantum advantages in specific, structured settings.
Recommended Textbooks
To supplement the lectures, the course draws from two seminal texts in the field:
- Nielsen & Chuang: Quantum Computation and Quantum Information (often called the "bible" of quantum computing).
- Kaye, Laflamme & Mosca: An Introduction to Quantum Computing.
This course, through its structured journey from quantum weirdness to the cutting-edge query complexity of partial functions, offers a unparalleled deep dive into why quantum computing is powerful, where that power comes from, and what its ultimate theoretical limitations might be. It is an essential intellectual journey for anyone serious about the future of computation.
Enroll Now →