



01550nas a2200133   4500008004100000245008300041210006900124260001400193520111400207100002001321700002201341700001601363856003701379       2024                        eng d00aPolynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth0 aPolynomialTime Classical Simulation of Noisy IQP Circuits with C  c3/21/20243 a<p>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, whose depth is greater than a critical O(1) threshold, the output distribution can be efficiently sampled by a classical computer. Unlike other simulation algorithms for quantum supremacy tasks, we do not require assumptions on the circuit&#39;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.</p>1 aRajakumar, Joel1 aWatson, James, D.1 aLiu, Yi-Kai  uhttps://arxiv.org/abs/2403.14607