One of the great insights of cryptography and computational complexity is the notion of computationally-bounded algorithms, which allow us to reason about properties that would otherwise be impossible to achieve. Could these ideas also be relevant to quantum information and quantum mechanics? In this talk, we discuss how computational thinking changes the landscape of quantum cryptography: What primitives can we construct, how definitions change, and what are the outstanding open problems. If time permits, we will also discuss new foundational questions on quantum information, motivated by cryptographic applications.