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
- Divesh Aggarwal(Principal Investigator)
- Hartmut Klauck(Principal Investigator)
- Miklos Santha(Principal Investigator)
- Rahul Jain(Principal Investigator)
- Patrick Rebentrost(Senior Research Fellow)
- Han-Hsuan Lin(Research Fellow (NTU))
- Hoeteck Wee(Research Affiliate)
- Iordanis Kerenidis(Research Affiliate)
- Li Jianwei(Research Fellow)
- Maciej Obremski(Research Fellow)
- Naqueeb Warsi(Research Fellow)
- Erick Purwanto(Research Assistant)
- Debbie Lim Huey Chih(CQT PhD Student)
- Kapshikar Upendra Shamrao(CQT PhD Student)
- Maharshi Ray(CQT PhD Student)
- Naresh Goud Boddu(CQT PhD Student)
- Srijita Kundu(CQT PhD Student)
- Yang Siyi(CQT PhD Student)
- Yohanes Yudhi Adikusuma(PhD Student (SoC, NUS))
- Antoine Joux(Visiting Research Professor)
- Gabor Ivanyos(Visiting Research Associate Professor)
- Serge Massar(Visiting Research Professor)
- Troy Lee(Visiting Research Associate Professor)
- Dmitry Gavinsky(Visiting Senior Research Fellow)
- Itai Arad(Visiting Senior Research Fellow)
- Marco Tomamichel(Visiting Senior Research Fellow)
- Thomas Vidick(Visiting Senior Research Fellow)
Recent papers
- Gábor Ivanyos, Péter Kutas, Lajos Rónyai. (2019). Explicit equivalence of quadratic forms over $\\mathbb{F}_q(t)$. Finite Fields and Their Applications 55 33-63
- Gábor Ivanyos, Youming Qiao. (2019). Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing. SIAM Journal of Computing 48 926-963
- Y. Wang, I.W. Primaatmaja, E. Lavie, A.Varvitsiotis, C.C.W. Lim. (2019). Characterising the correlations of prepare-and-measure quantum networks. NPJ: Quantum Information 5 17
- A. Anshu, R. Jain, NA Warsi. (2019). On the near-optimality of one-shot classical communication over quantum channels. J. Math. Phys.
- A. Anshu, R. Jain, NA Warsi. (2019). Building blocks for communication over noisy quantum networks. IEEE Transactions on Information Theory 65 1287-1306
- A. Anshu, R. Jain, NA Warsi. (2019). A hypothesis testing approach for communication over entanglement assisted compound quantum channel. IEEE Transactions on Information Theory 65 2623-2636
- A. Anshu, Mario Berta, R. Jain, Marco Tomamichel. (2019). Partially smoothed information measures. IEEE ISIT
- A. Anshu, R. Jain, NA Warsi. (2019). One-shot measurement compression with quantum side information using shared randomness.. IEEE Transactions on Information Theory
- Sevag Gharibian, Justin Yirka, Aarthi Sundaram, Jamie Sikora, M. Santha. (2018). Quantum generalizations of the polynomial hierarchy with applications to QMA(2). International Symposium MFCS 1-16
- Gábor Ivanyos, Lajos Rónyai, Péter Kutas. (2018). Computing explicit isomorphisms with full matrix algebras over $\mathbb{F}_q(x)$. Foundations of Computational Mathematics 18 381-397
- Gábor Ivanyos, K. V. Subrahmanyam, Youming Qiao. (2018). Constructive noncommutative rank computation is in deterministic polynomial time. Computational Complexity 27 561–593
- Youming Qiao, K. V. Subrahmanyam, Gábor Ivanyos. (2018). Constructive noncommutative rank computation is in deterministic polynomial time. Computational Complexity 27 561-593
- 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
