NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.

Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.

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 October 8, 2025)

Issues

If you have any questions about this publication or are having problems accessing it, please contact [email protected].

Created January 12, 2025, Updated March 6, 2025
Was this page helpful?