Quantum Algorithms

Quantum computation has been a very active research area for the past decade. Feynman initiated the idea of building a computer that exploits laws of quantum mechanics in order to solve computing problems that could not be solved efficiently on classical computers. Today, two main results lend credence to this model of computation. P. Shor gave a quantum algorithm that, in polynomial time, decomposes any integer into its prime factors, whereas no such algorithm is known in the classical models of computation. Indeed, that best classical algorithms need exponential time to factorize. This renders vulnerable to quantum computers the main public key cryptosystems, such as RSA. A few years later, L. Grover designed an algorithm that finds any marked element in an unstructured list, and whose running time quadratically improves over the best possible randomized algorithm. The main motivation for a quantum computer, illustrated by the above results, is to solve tasks more efficiently than classically. While the ultimate goal is an exponential improvement, polynomial speedups are also very useful, and certainly are worth of investigation. This research projects targets both types of improvements over classical computing, among others in the field of group theoretical algorithms and quantum walk based search procedures.

Communication Complexity, Query Complexity and other aspects of communication

Communication complexity right from its advent in late 70's has been a very active area of research in Theoretical Computer Science. It is one area with very significant and far reaching connections with other areas of complexity theory. This projects intends to explore this area more both in the classical and quantum settings and attempts to attack some of the key questions still remaining open and possibly discover other interesting connections with other areas of complexity theory. This project includes in its scope studying other aspects of classical and quantum communication which do not fall under the umbrella of communication complexity e.g. Remote State Preparation etc.

Interactive Proofs, Zero Knowledge, Quantum Games

The aim of this project is to study some of the primary areas in quantum complexity theory that have developed well over the last couple of years including Interactive Proofs, Zero Knowledge Proofs. Quantum Games like Non-Local games and Quantum Zero-Sum games have also found attention in recent research and their study sometimes is instrumental in arriving at some Structural Complexity results like understanding power of some complexity classes.

Project Reports