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.

arXiv comment5 pages, 1 figure

References in corpus (22)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Logical quantum processor based on reconfigurable atom arrays
• Simulating quantum computation by contracting tensor networks
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Interacting Quantum Observables: Categorical Algebra and Diagrammatics
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Trading classical and quantum computational resources
• Average-case complexity versus approximate simulation of commuting quantum computations
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Instantaneous Quantum Computation
• Reducing T-count with the ZX-calculus
• Solving the sampling problem of the Sycamore quantum circuits
• Exact Algorithms for Maximum Independent Set
• The ZX-calculus is complete for stabilizer quantum mechanics
• There and back again: A circuit extraction tale
• How many qubits are needed for quantum computational supremacy?
• 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