U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

PUBLICATIONS

Polynomial-Time Classical Simulation of Noisy IQP Circuits after Constant Depth

Published

Author(s)

Joel Rajakumar, James Watson, Yi-Kai Liu

Abstract

Sampling from the output distributions of quantum computations comprising only commuting gates, known as instantaneous quantum polynomial (IQP) computations, is believed to be intractable for classical computers, and hence this task has become a leading candidate for testing the capabilities of quantum devices. Here we demonstrate that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, the output distribution can be efficiently sampled by a classical computer after a critical O(1) depth. Unlike other simulation algorithms for quantum supremacy tasks, we do not require assumptions on the circuit's architecture, on anti-concentration properties, nor do we require Ω(log(n)) circuit depth. We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit. Our results suggest that quantum supremacy experiments based on IQP circuits may be more susceptible to classical simulation than previously thought.
Proceedings Title
Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
Conference Dates
January 12-15, 2025
Conference Location
New Orleans, LA, US
Conference Title
ACM-SIAM Symposium on Discrete Algorithms (SODA)
Pub Type
Conferences

Download Paper

https://doi.org/10.1137/1.9781611978322.30
Local Download

Keywords

Quantum computing, computational complexity theory, quantum error correction, random sampling
Quantum information science and Computational science

Citation

Rajakumar, J. , Watson, J. and Liu, Y. (2025), Polynomial-Time Classical Simulation of Noisy IQP Circuits after Constant Depth, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA, US, [online], https://doi.org/10.1137/1.9781611978322.30, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=957649 (Accessed April 10, 2025)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created January 12, 2025, Updated March 6, 2025