Many families of quantum circuits produce output distributions that classical computers cannot efficiently approximate, assuming standard complexity-theoretic or cryptographic conjectures (examples include Shor's algorithm or simulating quantum systems). However, near-term quantum computers are inherently noisy and often lack key features needed for fault-tolerant implementations, 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 efficient in some cases. We are also getting at a more fundamental question here, can unitary (i.e. reversible) quantum processes retain computational complexity when exposed to a constant rate of noise or decoherence? In this proposal, we explore how practical constraints, such as limited connectivity between qubits and restricted gate sets, further limit the computational power of noisy quantum circuits. Our goal is to clearly delineate regimes in which quantum advantage is or isn't possible, in the presence of noise. We present results on both fronts, offering evidence for computational hardness in some settings while establishing classical simulatability in others.