With the ultimate goal of violating the Extended Church-Turing Thesis, the quest to build quantum computers is deeply rooted in complexity theory. However, three decades of quantum complexity theory have largely focused on quantum algorithms for classical computing tasks -- those with classical inputs and outputs. Recently there has been increasing interest in studying the computational difficulty of inherently quantum tasks (i.e., those with quantum inputs and/or outputs). There are diverse examples of such tasks, like preparing ground states of Hamiltonians, breaking quantum cryptographic protocols, and decoding the Hawking radiation of black holes. Many techniques and approaches from traditional complexity theory are inadequate for reasoning about such computational tasks, suggesting a need for an "inherently quantum" complexity theory.

In this talk I will discuss some facets and themes of a complexity theory for the Quantum Age. The talk will have many more questions than answers, and will not assume background in complexity theory.