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: http://cs.quantumlah.org/

Group Members

Recent papers

  • Shengyu Zhang, M. Santha, Tongyang Li, T. Lee. (2021). On the cut dimension of a graph. 200 15:1-15:35
  • Shengyu Zhang, M. Santha, T. Lee. (2021). Quantum algorithms for graph problems with cut queries. 939-958
  • Xin Wang, Maharshi Ray, Yassine Hamoudi, Frank Patrick Rebentrost, M. Santha, Siyi Yang. (2021). Quantum algorithms for hedging and the learning of Ising models. Phys. Rev. A 103
  • M. Santha, S. Massar. (2021). Total Functions in QMA. Quantum Information Processing 20
  • Ernest Tan, S.Kundu. Composably secure device-independent encryption with certified deletion.
  • Upendra S. Kapshikar, N.G. Boddu. Tamper Detection against Unitary Operators.
  • Shalev Ben-David, Anurag Anshu, S.Kundu. (2021). On Query-to-Communication Lifting for Adversary Bounds.
  • N.G. Boddu, D. Aggarwal, Maciej Lukasz Obremski, R. Jain. Quantum Measurement Adversary.
  • S.Kundu, R. Jain. A direct product theorem for quantum communication complexity with applications to device-independent QKD.
  • Shima Bab Hadiashar, Anurag Anshu, Dave Touchette, Ashwin Nayak, R. Jain. (2021). One-shot quantum state redistribution and quantum Markov chains.
  • R. Jain. (2021). Chain-rules for channel capacity.
  • S.Kundu, R. Jain. (2021). A Direct Product Theorem for One-Way Quantum Communication.
  • M.Ray, N.G. Boddu, K. Bharti, L.C. Kwek, Adán Cabello. (2021). Graph-theoretic approach to dimension witnessing. New J. Phys. 23 033006
  • Raghav Kulkarni, Gábor Ivanyos, Aarthi Sundaram, M. Santha, Youming Qiao. (2018). On the Complexity of Trial and Error for Constraint Satisfaction Problems. Journal of Computer and System Sciences 92 48-64
  • Juris Smotrovs, T. Lee, Aleksandrs Belovs, Andris Ambainis, Kaspars Balodis, M. Santha. (2017). Separations in Query Complexity Based on Pointer Functions. JACM 64
more preprints > more publications >

We are hiring

hiring

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

go to Join Us >