Quantum Information Science (QIS) is a young, highly interdisciplinary field touching on the foundations of both computer science and quantum physics It provides a new model of computation that is both physically feasible and more powerful than conventional computing. If a quantum computer is built, we will be able to solve computational problems that are hard for ordinary computers. Quantum information also enables communication and cryptography protocols that are impossible in the classical world. These facts have created enormous interest in QIS.We propose research on computer science aspects of QIS, with a strong interdisciplinary collaboration between computer scientists and physicists that makes our consortium unique in Europe. We will apply ideas from computer science to solve problems in quantum information science and the ideas from quantum information and physics to solve problems in classical computer science.Our goals include new methods for building quantum algorithms (e.g., by harnessing quantumwalks) and understanding the general structure of quantum algorithms (e.g., the interplay between their quantum and classical components). In quantum communication, we will integrate the computer science and physics perspectives, with implications for a variety of models: quantum games, communication complexity, interactive proofs and cryptographic protocols.We will also study the mathematical structures that are common to classical and quantum computing, with applications to both fields.We believe that our approach is the most timely answer to:A) the challenges presently facing the theory of QIS which needs both a strengthening of its foundations and the development of new applications; andB) the exciting but as yet barely explored opportunity of applying the new tools developpedwithin QIS to classical computer science.