  Noise is the defining feature of the NISQ era, but it remains unclear if
noisy quantum devices are capable of quantum speedups. Quantum supremacy
experiments have been a major step forward, but gaps remain between the theory
behind these experiments and their actual implementations. In this work we
initiate the study of the complexity of quantum random circuit sampling
experiments with realistic amounts of noise.
  Actual quantum supremacy experiments have high levels of uncorrected noise
and exponentially decaying fidelities. It is natural to ask if there is any
signal of exponential complexity in these highly noisy devices. Surprisingly,
we show that it remains hard to compute the output probabilities of noisy
random quantum circuits without error correction. More formally, so long as the
noise rate of the device is below the error detection threshold, we show it is
#P-hard to compute the output probabilities of random circuits with a constant
rate of noise per gate. This hardness persists even though these probabilities
are exponentially close to uniform.
  Interestingly these hardness results also have implications for the
complexity of experiments in a low-noise setting. The issue here is that prior
hardness results for computing output probabilities of random circuits are not
robust enough to imprecision to connect with the Stockmeyer argument for
hardness of sampling from circuits with constant fidelity. We exponentially
improve the robustness of prior results to imprecision, both in the cases of
Random Circuit Sampling and BosonSampling. In the latter case we bring the
proven hardness within a constant factor in the exponent of the robustness
required for hardness of sampling for the first time. We then show that our
results are in tension with one another -- the high-noise result implies the
low-noise result is essentially optimal, even with generalizations of our
techniques.
