Quantum information science combines quantum physics and computer science to achieve advantages over conventional information processing (for example, speeding up various computing tasks ranging from simulating physical systems to factoring and searching).During recent years we have seen significant progress in creating a quantum computer. At the same time, progress in the development of new quantum algorithms has been rather slow. The aim of the project is to find new examples where quantum computers are better than traditional computers in solving practically important computing tasks. The following actions are planned:1. Development of new quantum algorithms. Quantum algorithms for well-known computational task classes (e.g. optimisation and machine learning problems) will be developed. Recently developed methods will be used to achieve this goal, from analysis of quantum algorithms through semi-definito programming to quantum algorithms to address linear equation systems and new methods developed.2. Determination of quantum computational limits. The maximum potential advantage of quantum computers in different models, from complexity classes to querying and communication complexity, will be assessed.3. Development of experiments on quantum computing. Experiments on medium size quantum computers (50-300 quantum bits without error correction) will be created. The best way to demonstrate the superiority of a quantum computer with this kind of quantum computer will be explored. As Google is planning to create a 49 quantum bit quantum computer in the coming months, it is very important to create a theoretical experiment for this kind of quantum computer.4. Links with classical computer science/mathematics. Opportunities will be explored how complex mathematical methods from classical computer science can be used to solve problems in quantum computing or, in the opposite direction, completely classic problems in computer science can be solved through quantum computing in unexpected ways. Duration of the project: 58 months. Start of the project – February 2019, deadline: 30 November 2023. Total cost: EUR 1645000