Limitations of Noisy Quantum Devices in Computational and Entangling Power

Finding solid and practical quantum advantages via noisy quantum devices without error correction is a critical but challenging problem. On the flip side, it is important to study the general limitations of noisy quantum devices with the help of classical computers. For computation with general classical processing, we show that noisy quantum devices with a circuit depth of more than O(log (n)) provide no advantages in any quantum algorithms for decision problems. Our result rigorously rules out the possibility of implementing well-known quantum algorithms, including Shor's, Grover's, Harrow-Hassidim-Lloyd, and linear-depth variational algorithms. Then, we study the maximal entanglement generation of noisy quantum devices with one- and two-dimensional qubit connections. In particular, we show an upper bound of O(log (n)) for a one-dimensional qubit chain. This finding highlights the restraints for quantum simulation and scalability regarding entanglement growth.