Characterizing Entanglement and Quantum Advantage Using Physical Complexity Theory

This dissertation develops physical complexity theory: the use of computational complexity and theoretical computer science to study questions that are directly motivated by physics. The thesis is organized into three parts. Part I studies entanglement, showing how computationally bounded observers can fail to distinguish low-entanglement states from highly entangled ones, and how entanglement can generate sharp transitions in simulation complexity. Part II studies quantum advantage through the lenses of realistic noise and verification. Part III turns toward useful quantum advantage, connecting the hardness of learning quantum circuits to quantum cryptography. Together, these results illustrate how complexity theory can uncover physical structure that is invisible to purely information-theoretic or idealized models.