Classically simulating intermediate-scale instantaneous quantum polynomial circuits through a random graph approach

Quantum advantage is a demonstration of a computation by a quantum computer that cannot 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 advantage with random circuit sampling is to use instantaneous quantum polynomial (IQP) circuits. These are quantum circuits where the unitary it implements is diagonal. In this paper, we introduce improved techniques for exactly 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\Big(\frac{{\text{log}^2 n}}{n}2^n\Big)$, which for sparse circuits (where each qubit interacts with $O(\text{log} n)$ other qubits) runs in $o(2^n/\text{poly} (n))$ for any given polynomial. Using a more complicated stabilizer decomposition approach we improve the algorithm for dense circuits to $O\Big(\frac{(\text{log} n)^{4-β}}{n^{2-β}}2^n\Big)$ where $β≈0.396$. We further discuss how our techniques also lead to improved simulation times for IQP circuits on restricted architectures. We benchmarked our main algorithm and found that we can simulate up to 50-qubit circuits in a couple of minutes on a laptop, with 68-qubit sparse circuits taking a couple of hours. We estimate dense 70-qubit circuits are in range for large computing clusters.

• View at Publisher