  It is imperative that useful quantum computers be very difficult to simulate
classically; otherwise classical computers could be used for the applications
envisioned for the quantum ones. Perfect quantum computers are unarguably
exponentially difficult to simulate: the classical resources required grow
exponentially with the number of qubits $N$ or the depth $D$ of the circuit.
Real quantum computing devices, however, are characterized by an exponentially
decaying fidelity $\mathcal{F} \sim (1-\epsilon)^{ND}$ with an error rate
$\epsilon$ per operation as small as $\approx 1\%$ for current devices. In this
work, we demonstrate that real quantum computers can be simulated at a tiny
fraction of the cost that would be needed for a perfect quantum computer. Our
algorithms compress the representations of quantum wavefunctions using matrix
product states (MPS), which capture states with low to moderate entanglement
very accurately. This compression introduces a finite error rate $\epsilon$ so
that the algorithms closely mimic the behavior of real quantum computing
devices. The computing time of our algorithm increases only linearly with $N$
and $D$. We illustrate our algorithms with simulations of random circuits for
qubits connected in both one and two dimensional lattices. We find that
$\epsilon$ can be decreased at a polynomial cost in computing power down to a
minimum error $\epsilon_\infty$. Getting below $\epsilon_\infty$ requires
computing resources that increase exponentially with
$\epsilon_\infty/\epsilon$. For a two dimensional array of $N=54$ qubits and a
circuit with Control-Z gates, error rates better than state-of-the-art devices
can be obtained on a laptop in a few hours. For more complex gates such as a
swap gate followed by a controlled rotation, the error rate increases by a
factor three for similar computing time.
