  Quantum Supremacy is a demonstration of a computation by a quantum computer
that can not be performed by the best classical computer in a reasonable time.
A well-studied approach to demonstrating this on near-term quantum computers is
to use random circuit sampling. It has been suggested that a good candidate for
demonstrating quantum supremacy with random circuit sampling is to use
\emph{IQP circuits}. These are quantum circuits where the unitary it implements
is diagonal. In this paper we introduce improved techniques for classically
simulating random IQP circuits. We find a simple algorithm to calculate an
amplitude of an $n$-qubit IQP circuit with dense random two-qubit interactions
in time $O(\frac{\log^2 n}{n} 2^n )$, which for sparse circuits (where each
qubit interacts with $O(\log n)$ other qubits) runs in $o(2^n/\text{poly}(n))$
for any given polynomial. Using a more complicated stabiliser decomposition
approach we improve the algorithm for dense circuits to $O\left(\frac{(\log
n)^{4-\beta}}{n^{2-\beta}} 2^n \right)$ where $\beta \approx 0.396$. We
benchmarked our algorithm and found that we can simulate up to 50-qubit
circuits in a couple of minutes on a laptop. We estimate that 70-qubit circuits
are within reach for a large computing cluster.
