Last Update
07.01.2015 |

*Quantum mechanics and information and communication technologies (ICT)* are two of the biggest developments of the 20th century in science and technology. Quantum mechanics has allowed us to understand the physics of microworld, on the level of individual atoms and particles, where the laws of physics are fundamentally different from the conventional *(classical)* physics. ICT has transformed almost every aspect of our everyday lives.

*Quantum computing and quantum information science* brings these two fields together, by applying the effects of quantum mechanics to solve problems in computing and information processing. In last 20 years, quantum information science has become one of most dynamic fields of research, with many of the leading universities in the world having research groups in quantum information science.

Experimentally, physicists are finding ways to control physical systems on the level of individual atoms and particles. At the same time, computer scientists are discovering how to use the power of quantum mechanics for information processing. This has resulted in many surprising developments.

In 1990s, it was discovered that quantum algorithms *(such as Shor’s factoring algorithm)* can solve problems that are difficult for conventional computers. And quantum effects allow to design cryptographic protocols for key distribution that are provably secure, with the validity of quantum mechanics being the only assumption that is required for the security proof. Such strong degree of security is not possible in the classical world (where the security of cryptographic protocols relies on the hardness of factoring or, more generally, existence of one-way functions).

These discoveries sparked an enormous interest in both building a quantum computer and developing the theory of quantum information. Many more interesting developments have followed in the recent years, with quantum algorithms based on quantum walks *(quantum counterparts of random walks)*, quantum algorithms for formula evaluation and solving systems of linear equations and unexpected applications of quantum methods to study purely classical problems in computer science and even mathematical analysis.

At the same time, the field of quantum algorithms and quantum information is still quite young and it may be the case that the most important applications of quantum information science are still to be discovered. Quantum information has the potential for new, surprising results, either in the form of new quantum algorithms and communication protocols *(which would provide new applications for quantum technologies)* or in the form of unexpected, paradigm-changing applications of ideas from quantum information to other fields *(for example, to classical computer science or to studying the physics of quantum mechanical systems)*.

Our project investigates the following three big questions:

1. **New quantum algorithms.** What other problems can we solve on a quantum computer? More generally, can we come up with new methods for designing quantum algorithms?

2. **Structural questions about quantum algorithms. **When can we achieve large *(super-polynomial)* quantum speedups? What properties of a computational problem make this plausible?

3. **Applications of ideas from quantum information to other areas. **How can we use the ideas and mathematical methods from quantum information to solve problems in classical computer science? How can we use the ideas from theory of computing to study quantum physical systems?