2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/92595More than a speculative technology, quantum computing seems to challenge our most basic intuitions about how the physical world should behave. In this thesis I show that, while some intuitions from classical computer science must be jettisoned in the light of modern physics, many others emerge nearly unscathed; and I use powerful tools from computational complexity theory to help determine which are which.UC Berkeley PhD thesis, 258 pages. Some minor errors fixedQuantum PhysicsComputational Complexitytext