Research

The Theory of Computer Science group (TCS) investigates the theoretical foundations of computer science. TCS  connects to all the main research themes of the Informatics Institute, by researching fundamental questions such as: ‘How fast can a computer solve certain problems?’ (part of complexity theory), ‘How much information can be sent over a bad connection?’ (part of information theory) and ‘What are the power and limitations of a quantum computer?’ (part of quantum computing).

Their main focus is on three themes: quantum cryptography, quantum computing and information theory.

Quantum Cryptography
Recent progress in building quantum computers leads to new opportunities for cryptography, but also endangers existing cryptographic schemes. The research area of post-quantum cryptography investigates the possibilities for replacing currently used classical cryptography with quantum-secure variants. On the other hand, quantum computers introduce possibilities for new security technologies such as the secure delegation of a quantum computation to an untrusted server (in the quantum cloud) without compromising the privacy of the input data.

Quantum Computing
Using the benefits that quantum computers will have over classical computers, TCS can tackle problems in quantum chemistry, linear mathematical systems, and maybe even machine learning, that cannot be tackled by classical computers. In order to build quantum software for these new quantum computers, we need new tools like quantum programming languages and quantum compilers.

Information Theory 
A fundamental goal of information theory is to understand the inherent cost of making data resilient against errors by using error-correcting codes. Furthermore, an understanding of how data behave in the presence of noise plays a crucial role in many other parts of theoretical computer science. One connection they are actively investigating is with post-quantum cryptography, and a connection they hope to explore in the future is with fault-tolerant quantum computation.

Possible future applications of their research are more secure post-quantum cryptography, better quantum computers and more efficient telecommunications.

Facts & figures

The management of both the Informatics Institute and the ILLC have made it clear that a strong theory group is a necessary and integral part of the FNWI faculty. In 2022 they attracted two strong new staff members to change the course of the TCS group into a new direction.

The TCS group is part of a rather large community of theoretical computer science researchers in Amsterdam spread out over various institutions and research groups at UvA, VU and CWI (see overview). Most group members joined in 2021 and 2022, but they have already proven their quality, for example by previously obtaining personal grants such as VENI, VIDI, Rubicon, Marie Curie and NSERC.

Partnerships & collaborations

For the time being, the TCS group does not have concrete collaborations with public or private partners. However, group leader Christian Schaffner is also chair of the innovation hub Quantum.Amsterdam, which plays a role in setting up such collaborations between QuSoft and public-private partners. QuSoft has collaborations with ABN AMRO, Bosch, Toyota, IBM and others. Those collaborations focus on investigating practical use cases for quantum computing.

Education

The TCS group has an (almost) full-time teacher, Steven de Rooij, who teaches various theory courses in the Bachelor’s programme Informatica. We also teach Information Theory in the Bachelor’s programme Mathematics and the Master’s programme Logic and AI, and Modern Cryptography in the Bachelor’s programme Informatica, as well as a new course on Quantum Cryptography.

TCS will ensure that there is a strong theory component in the Bachelor’s and Master’s programmes in computer science. Furthermore, they have plans to set up an entirely new Master’s programme in Quantum Computer Science.

Future mission

Quantum computing research will continue to thrive over the coming years as more powerful hardware becomes available. This allows them to figure out whether and how to use quantum technology for useful applications. Simultaneously, the TCS group create awareness among decision-makers in business and public administration that they need to prepare for an update of their currently used (public-key) cryptography in order to be secure against future quantum attackers, for example Quantum Impact on Societal Security.

TCS has clear links with all the research themes AI, Computational Science, Data Science, and People, Society & Technology, and Systems & Networking.