Quantum computation has been put forward as a way to overcome current computational limits, by exploiting the quantum properties of nature. It is an interdisciplinary area at the interface of physics and computation. Since Shor's groundbreaking discovery in 1994 that a quantum computer can factor numbers efficiently, strong, steady advances have been made in understanding the advantages of quantum resources and numerous experimental efforts are underway to implement this model of computation. Our research goal is to expand our understanding of quantum resources and computation and its interplay with classical computation, as well as to open new directions. More specifically, we want to advance progress in algorithm design, using new paradigms we have recently helped to develop, and to deepen our understanding of the computational power of physical resources like shared quantum states (entanglement), quantum communication, quantum memory and restricted quantum systems. An important aspect of this proposal is to parallel this investigation into the power of quantum systems with a study of its limits. Specifically we want to identify potential hard problems for quantum computers and to explore their hardness properties as a base for new classical cryptosystems that are secure against quantum adversaries. We also want to deepen our understanding of the effects of an adversary with quantum resources in cryptography. In a society where information is a crucial economic resource it is important to protect today's information against tomorrow's possible progress in the implementation of quantum computers. In this line of research we also propose to explore the systematic use of the emerging toolbox of quantum techniques to find solutions for classical problems with quantum arguments.