Computer Science Group

Quantum mechanics and computer science are two of the biggest developments in the last century in science and technology: quantum mechanics gave us the opportunity to understand nature at the nanoscale, where the laws of physics are fundamentally different from the conventional (classical) physics; information technologies have revolutionized our everyday lives.

Quantum computing and quantum information science bring these fields together, applying quantum mechanics to problems in computing and communication. After Shor’s 1994 discovery of a quantum algorithm for factoring integers, which threatened the security of a widely-used encryption method, interest in quantum information science thrived. Other achievements of quantum information science include efficient and secure protocols for communication and cryptography. Those protocols have already resulted in quantum cryptography devices that are commercially available.

The computer science group’s activity covers a wide range of areas in quantum computing and information theory, often in close connection with related research areas in classical theoretical computer science. We mostly investigate quantum algorithms, complexity and quantum-safe cryptography. Quantum algorithms provide a recipe for efficiently solving practical problems on a quantum computer, of particular interest are problems which are difficult to solve on a classically. The study of quantum computational complexity is about understanding the fundamental limitations of information processing tasks in nature. By understanding such limits, it can offer a guide to crafting new algorithms and communication protocols. Quantum-safe cryptography is concerned with the design and the evaluation of cryptographic systems which are resistant even to quantum attacks.

More information at our homepage:

Group Members

Recent papers

  • Leonard Wossnig, Zhikuan Zhao, A.Prakash. (2018). A quantum linear system algorithm for dense matrices. Phys. Rev. Lett. 120 050502
  • H. Klauck. (2017). The Complexity of Quantum Disjointness. International Symposium MFCS 83 15:1-15:13
  • A.Prakash, Jamie William Jonathon Sikora, A.Varvitsiotis, Zhaohui Wei. (2017). Completely positive semidefinite rank. Mathematical Programming
  • Nitin Saxena, Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal. (2017). Irreducibility and r-th root finding over finite fields. ISSAC 37-44
  • A. Anshu, D. Gavinsky, R. Jain, S.Kundu, T. Lee, P. Mukhopadhyay, M. Santha, S. Sanyal. (2017). A Composition Theorem for Randomized Query Complexity. FSTTCS 2017
  • A. Anshu, R. Jain, N.A Warsi. (2017). A one-shot achievability result for quantum state redistribution. IEEE Transactions on Information Theory
  • A. Anshu, V. Krishna, R. Jain. (2017). Quantum Communication Using Coherent Rejection Sampling. Phys. Rev. Lett. 119 120506
  • A. Anshu. (2017). An upper bound on quantum capacity of unital channels. Proc. IEEE ITW
  • A. Anshu, Dave Touchette, P. Yao, Nengkun Yu. (2017). Exponential Separation of Quantum Communication and Classical Information. ACM STOC 277-288
  • A. Anshu, R. Jain, P. Mukhopadhyay, Ala Shayeghi, P. Yao. (2017). A new operational interpretation of relative entropy and trace distance between quantum states. IEEE Transactions on Information Theory
  • A. Anshu, Shalev Ben-David, Ankit Garg, R. Jain, Robin Kothari, T. Lee. (2017). Separating quantum communication and approximate rank. Proc. IEEE CCC
  • Jamie William Jonathon Sikora, A.Varvitsiotis. (2017). Linear conic formulations for two-party correlations and values of nonlocal games. Mathematical Programming 162 431-463
  • G. Ivanyos, M. Santha. (2017). On solving systems of diagonal polynomial equations over finite fields. Theoretical Computer Science 657 73-85
  • T. Lee, Frederic Magniez, M. Santha. (2017). Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing. Algorithmica 77 459-486
  • T. Lee, Z.H. Wei, Ronald de Wolf. (2017). Some upper and lower bounds on PSD-rank. Mathematical Programming 162 495--521
more publications >

We are hiring


Find out more about our PhD Positions on the Join us page.

go to Join Us >