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

  • D. Aggarwal, N. Stephens-Davidowitz. (2018). (Gap/S)ETH Hardness of SVP. ACM STOC
  • D. Aggarwal, A. Joux, A. Prakash, M. Santha. (2018). A new public-key cryptosystem via Mersenne numbers. CRYPTO
  • G. Ivanyos, Marek Karpinski, M. Santha, Nitin Saxena, Igor Shparlinski. (2018). Polynomial Interpolation and Identity Testing from High Powers over Finite Fields. Algorithmica 80 560-575
  • , Mathieu Bozzio, Adeline Orieux, Luis Trigo Vidarte, Isabelle Zaquine, I. Kerenidis, Eleni Diamanti. (2018). Experimental investigation of practical unforgeable quantum money. New J. Phys.
  • I. Arad, M. Santha, Aarthi Sundaram, Shengyu Zhang. (2018). Linear time algorithm for quantum 2SAT. Theory of Computing 1-27
  • A. Anshu, R. Jain, NA Warsi. (2018). Building blocks for communication over noisy quantum networks. IEEE Transactions on Information Theory
  • Y. Qiao, G. Ivanyos. (2018). Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing. ACM SIAM SODA 2357-2376
  • A. Anshu, Min-Hsiu Hsieh, R. Jain. (2018). Quantifying resource in catalytic resource theory. Phys. Rev. Lett.
  • , Leonard Wossnig, Zhikuan Zhao, A.Prakash. (2018). A quantum linear system algorithm for dense matrices. Phys. Rev. Lett. 120 050502
  • Leonard Wossnig, Zhikuan Zhao, Anupam Prakash. (2018). A quantum linear system algorithm for dense matrices. Phys. Rev. Lett. 120
  • Youming Qiao, G. Ivanyos. (2018). Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing. Symposium on Discrete Algorithms 2357-2376
  • D. Aggarwal, Noah Stephens-Davidowitz. (2018). Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP). Proceedings of the Symposium on Simplicity in Algorithms
  • A. Anshu, R. Jain, NA Warsi. (2018). A generalized quantum Slepian-Wolf. IEEE Transactions on Information Theory
  • A. Anshu, R. Jain, NA Warsi. (2018). A one-shot achievability result for quantum state redistribution. IEEE Transactions on Information Theory
  • , A. Anshu, Ankit Garg, Aram Harrow, P. Yao. (2018). Expected communication cost of distributed quantum tasks. IEEE Transactions on Information Theory
more publications >

We are hiring

hiring

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

go to Join Us >