Classically Simulating Quantum Supremacy IQP Circuits trough a Random Graph Approach

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((log²n/n)2ⁿ), which for sparse circuits (where each qubit interacts with O(log n) other qubits) runs in o(2ⁿ/poly(n)) for any given polynomial. Using a more complicated stabiliser decomposition approach we improve the algorithm for dense circuits to O(((log n)^4−β/n^2−β)2ⁿ) where β≈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.