  As quantum computers improve in the number of qubits and fidelity, the
question of when they surpass state-of-the-art classical computation for a
well-defined computational task is attracting much attention. The leading
candidate task for this milestone entails sampling from the output distribution
defined by a random quantum circuit. We develop a massively-parallel simulation
tool Rollright that does not require inter-process communication (IPC) or
proprietary hardware. We also develop two ways to trade circuit fidelity for
computational speedups, so as to match the fidelity of a given quantum computer
--- a task previously thought impossible. We report massive speedups for the
sampling task over prior software from Microsoft, IBM, Alibaba and Google, as
well as supercomputer and GPU-based simulations. By using publicly available
Google Cloud Computing, we price such simulations and enable comparisons by
total cost across hardware platforms. We simulate approximate sampling from the
output of a circuit with 7x8 qubits and depth 1+40+1 by producing one million
bitstring probabilities with fidelity 0.5%, at an estimated cost of $35184. The
simulation costs scale linearly with fidelity, and using this scaling we
estimate that extending circuit depth to 1+48+1 increases costs to one million
dollars. Scaling the simulation to 10M bitstring probabilities needed for
sampling 1M bitstrings helps comparing simulation to quantum computers. We
describe refinements in benchmarks that slow down leading simulators, halving
the circuit depth that can be simulated within the same time.
