Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach

Abstract

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.

5 pages, 1 figure

References in corpus (9)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Logical quantum processor based on reconfigurable atom arrays
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Solving the sampling problem of the Sycamore quantum circuits
• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
• Improved upper bounds on the stabilizer rank of magic states
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• How to simulate quantum measurement without computing marginals
• Simulating quantum circuits using efficient tensor network contraction algorithms with subexponential upper bound