Research Directions:
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 for factorizing integers run in sub-exponential time. This renders vulnerable to quantum computers the most widely used 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. This line of research targets such improvements of quantum computing over classical computing, among others, in the field of group theoretical algorithms and quantum walk based search procedures.
Quantum Machine Learning
Machine learning impacts society in areas such as autonomous vehicles, the internet of things, and e-commerce. Early breakthroughs such as Shor’s, Grover’s, and other algorithms promise quantum advantages for a substantial range of applications. The line of research on quantum machine learning explores the interface of quantum information, quantum computing, and machine learning. At the high level, efforts include designing quantum algorithms, developing fundamentally new algorithmic building blocks, and understanding more deeply the power of quantum computers. Specific focus areas include linear algebra problems such as matrix inversion, principal component analysis, and singular value transformations and optimization problems such as linear/semidefinite programming, support vector machines, generalised linear models, and neural networks. Another focus area is the design and implementation of quantum machine learning algorithms on presently available and near-term quantum computers. Such efforts have the potential to translate into quantum advantages for machine learning, AI, and optimisation.
Quantum-safe cryptography
Given the recent advances in quantum computing, Shor's algorithm poses a serious threat to all public-key cryptosystems that are currently used in practice. In the last couple of decades, some presumably quantum-safe public-key cryptosystems have been proposed in the literature. Perhaps the most promising among these are those based on the hardness of lattice problems like Learning with Errors (LWE) based cryptosystems and NTRU. While these cryptosystems have so far resisted any classical or quantum attacks, it cannot be excluded that such attacks are possible in the future. In particular, there is no unifying complexity-theoretic assumption (like NP-hardness) that relates the difficulty of breaking all these cryptosystems. Thus, it is desirable to both come up with promising new proposals for public-key cryptosystems, and also to study (limitations of) both classical and quantum algorithms for breaking existing proposals of quantum-safe cryptosystems. The goal of this line of research is to make progress in both these directions.
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 direction of research 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.