Inherently quantum lower bounds on computational complexity

Computational complexity theory is usually phrased in terms of decision problems and Boolean functions, whose inputs and outputs are purely classical. However, many quantum computational tasks motivated by physics, machine learning, and cryptography involve operation on quantum information in a fundamental way. In this dissertation, we investigate the complexity of various "inherently quantum" computational tasks that have no classical analogue. In particular, we (1) introduce new tools for proving lower bounds on quantum query complexity augmented with quantum states and unitary transformations, (2) establish black-box separations in structural complexity that illustrate fundamental differences between classical and quantum randomness, and (3) construct relativized instantiations of quantum cryptographic primitives that do not rely on one-way functions. We prove these results through the framework of quantum query complexity and its generalizations.Computer Science