Quantum mechanics and general relativity are the two pillars of 20th-century physics. However, paradoxes arise when we attempt to combine these theories to arrive at a quantum theory of space and time, often because the appearance of black holes and spacetime singularities seem to destroy quantum information. I will discuss how we can resolve these paradoxes by drawing on concepts of complexity and information from theoretical computer science, communications theory, and cryptography. I will use techniques from these fields to explain diverse, interlinked aspects of fundamental physics, including: the dynamics of quantum chaos and thermalization; the recovery of information from beyond the horizon of black holes; and, most fundamentally, causality in physical processes.