# Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach

Article · Julien Codsi, John van de Wetering

- Archive id: arxiv:2212.08609
- Published: 2022-12-16
- Venue: Phys. Rev. A 111, 012422. 2025
- DOI: https://doi.org/10.1103/physreva.111.012422
- arXiv: https://arxiv.org/abs/2212.08609
- Citations: 4
- Source URL: https://arxiv.org/abs/2212.08609
- PDF: https://arxiv.org/pdf/2212.08609
- Provenance: arxiv

## 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-β}}{n^{2-β}} 2^n \\right)$ where $β\\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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Quantum Algorithms & Quantum Advantage](https://space-kitty.com/topics/quantum-algorithms-advantage)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.