Limitations of noisy quantum devices in computing and entangling power

Abstract Finding solid and practical quantum advantages via noisy quantum devices without error correction is a critical but challenging problem. Conversely, comprehending the fundamental limitations of the state-of-the-art is equally crucial. In this work, we consider the class of strictly contractive unital noise and derive its analytical representation by decomposition. Under such noise, we observe the polynomial-time indistinguishability of n -qubit devices from random coins when circuit depths exceed $$\Omega (\log (n))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:mi>log</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Even with classical processing, we demonstrate the absence of computational advantage in polynomial-time algorithms with super-logarithmic noisy circuit depths. These results impact variational quantum algorithms, error mitigation, and quantum simulation with polynomial depth. Furthermore, we consider noisy quantum devices with a restricted gate topology. For one-dimensional noisy qubit circuits, we rule out super-polynomial quantum advantages in all-depth regimes. We also establish upper limits on entanglement generation: $$O(\log (n))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>log</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> for one-dimensional circuits and $$O(\sqrt{n}\log (n))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msqrt> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:msqrt> <mml:mi>log</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> for two-dimensional circuits. Our findings underscore the computational capacity and entanglement scalability constraints in noisy quantum devices.