Many families of quantum circuits, when run on an ideal (or fault-tolerant) quantum computer, produce outputs sampled from probability distributions that cannot be reproduced (exactly or approximately) on classical computers, assuming standard complexity-theoretic or cryptographic conjectures. Examples include Shor's algorithm for factoring integers and the simulation of quantum systems. This is called "quantum advantage."

However, near-term quantum computers are inherently noisy and often lack key features needed for fault-tolerant quantum computation, such as the ability to reset qubits quickly or adapt based on measurement outcomes. Without these tools to remove entropy, the output distributions of noisy quantum circuits quickly become indistinguishable from uniform randomness under realistic noise models. This raises an important question: are there families of noisy quantum circuits that remain hard to classically simulate, at least for short time-scales, before noise drives them to complete randomness? This question has significance beyond the near-term regime, because even when large fault-tolerant devices become available, simpler noisy circuits may be more space and time efficient for some use cases. This also hints at a more fundamental question: how long can unitary (i.e. reversible) quantum processes retain computational complexity when exposed to a constant rate of noise or decoherence?

In this thesis, we explore how practical constraints, such as limited connectivity between qubits and restricted gate sets, further limit the computational power of noisy quantum circuits. We clearly delineate regimes in which quantum advantage is or isn't possible in the presence of noise. An overarching idea behind our results is that the output states of noisy quantum circuits resemble thermal states (quantum systems in equilibrium with an environment at a finite temperature). This mapping allows computational hardness results for quantum circuits to be imported to the thermal state setting, and classical simulation techniques to be imported from the thermal state setting to quantum circuits. Thus, we present results on both fronts, establishing quantum advantage in some settings while establishing no-go theorems in others.