Module 1 (14 Hours)
Review of Linear Algebra. The postulates of quantum mechanics. Review of Theory of Finite Dimensional Hilbert Spaces and Tensor Products
Module 2 (14 Hours)
Complexity classes. Models for Quantum Computation. Qubits. Single and multiple qubit gates. Quantum circuits. Bell states. Single qubit operations. Controlled operations and measurement. Universal quantum gates. Quantum Complexity classes and relationship with classical complexity classes
Module 3 (14 Hours)
Quantum Algorithms – Quantum search algorithm - geometric visualization and performance. Quantum search as a
quantum simulation. Speeding up the solution of NP Complete problems. Quantum search as an
unstructured database. Grover’s and Shor’s Algorithms.
Module 4 (14 Hours)
Introduction to Quantum Coding Theory. Quantum error correction. The Shor code. Discretization of errors, Independent error models, Degenerate Codes. The quantum Hamming bound. Constructing quantum codes – Classical linear codes, Shannon entropy and Von Neuman Entropy.
References:
1. Nielsen, Michael A., and Isaac L. Chuang, Quantum Computation and Quantum Information. Cambridge, UK, Cambridge University Press, 2002.
2. Gruska, J. Quantum Computing, McGraw Hill, 1999.
3. Halmos, P. R. Finite Dimensional Vector Spaces, Van Nostrand, 1958.
4. Peres, Asher. Quantum Theory: Concepts and Methods. Springer, 1993.
CS4029 TOPICS IN THEORY OF COMPUTATION
Pre-requisite: CS3001 Theory of Computation
-
Total Hours: 56 Hrs
Module 1 (14 Hours)
Recursion, The primitive recursive functions, Turing machines, Arithmetization, Coding functions , The normal form theorem, The basic equivalence and Church’s thesis, Canonical coding of finite sets, Computable and computably enumerable sets, Diagonalization, Computably enumerable sets , Undecidable sets , Uniformity, Many-one reducibility, The recursion theorem, Proof for Godel’s Incompleteness Theorem based on Recursion theorem.
Module 2 (14 Hours)
The arithmetical hierarchy, Computing levels in the arithmetical hierarchy , Relativized computation and Turing degrees, Turing reducibility , Limit computable sets, Incomparable degrees
Module 3 (14 Hours)
The priority method, Diagonalization, Turing incomparable sets , Undecidability , Constructivism, randomness and Kolmogorov complexity, Compressibility and randomness, Undecidability
Module 4 (14 Hours)
Scheme, programming and computability theory based on a term-rewriting, "substitution" model of computation by Scheme programs with side-effects; computation as algebraic manipulation: Scheme evaluation as algebraic manipulation and term rewriting theory.
References:
-
R. I. Soare, Recursively enumerable sets and degrees, Springer-Verlag, 1987.
-
G. E. Sacks, Higher recursion theory, Springer Verlag, 1990.
-
M. Li and P. Vitányi, An introduction to Kolmogorov complexity and its applications, Springer-Verlag, 1993.
-
Dexter C. Kozen, Automata and Computability, Springer-Verlag, 1997.
-
S. C. Kleene, Introduction to Metamathematics, Van Nostrand, 1950.
-
MIT OpenCourseWare on Computability Theory of and with Scheme at http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-844-computability-theory-of-and-with-scheme-spring-2003/ Accessed on 26/11/2010
CS4030 COMPUTATIONAL COMPLEXITY
Pre-requisite: Nil
-
Total Hours: 56 Hrs
Module 1 (14 Hours)
Review of Complexity Classes, NP and NP Completeness, Space Complexity, Hierarchies, Circuit satisfiability, Savitch and Immerman theorems, Karp Lipton Theorem.
Module 2 (14 Hours)
Randomized Complexity classes, Adleman's theorem, Sipser Gacs theorem, Randomized Reductions, Counting Complexity, Permanent’s and Valiant’s Theorem
Module 3 (14 Hours)
Parallel complexity, P-completeness, Sup-liner space classes, Renegold's theorem, Polynomial hierarchy and Toda's theorem
Module 4 (14 Hours)
Arthur Merlin games, Graph Isomorphism problem, Goldwasser-Sipser theorem, Interactive Proofs, Shamir's theorem.
References:
-
S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
-
Papadimtriou C. H.., Computational Complexity, Addison Wesley, 1993.
-
Motwani R, Randomized Algorithms, Cambridge University Press, 1995.
-
Vazirani V., Approximation Algorithms, Springer, 2004.
CS4031 COMPUTATIONAL ALGEBRA
Pre-requisite: Nil
-
Total Hours: 70 Hrs
Dostları ilə paylaş: |