Limitations of Noisy Quantum Devices in Computational 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))$. 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))$ for one-dimensional circuits and $O(\sqrt{n}\log (n))$ for two-dimensional circuits. Our findings underscore the computational capacity and entanglement scalability constraints in noisy quantum devices.

23 pages, 7 figures

References in corpus (46)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithm for solving linear systems of equations
• Variational Quantum Algorithms
• Quantum computational chemistry
• Error mitigation for short-depth quantum circuits
• Strong quantum computational advantage using a superconducting quantum processor
• Suppressing quantum errors by scaling a surface code logical qubit
• Logical quantum processor based on reconfigurable atom arrays
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• Quantum Error Mitigation
• Classical simulation of quantum many-body systems with a tree tensor network
• Eigenstate Thermalization Hypothesis
• Hybrid quantum-classical algorithms and quantum error mitigation
• Simulating quantum computation by contracting tensor networks
• Resilient Quantum Computation: Error Models and Thresholds
• Realization of an Error-Correcting Surface Code with Superconducting Qubits
• Demonstration of fault-tolerant universal quantum gate operations
• Fault-tolerant operation of a logical qubit in a diamond quantum processor
• Beating the break-even point with a discrete-variable-encoded logical qubit
• Fundamental limits of quantum error mitigation
• Quantum advantage with noisy shallow circuits in 3D
• Quantum logarithmic Sobolev inequalities and rapid mixing
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Entanglement rates and area laws
• Thermodynamic entropy of a many body energy eigenstate
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• Exploring Large-Scale Entanglement in Quantum Simulation
• A polynomial-time classical algorithm for noisy random circuit sampling
• Classical algorithms for quantum mean values
• Entangling power and quantum circuit complexity
• Universal Sampling Lower Bounds for Quantum Error Mitigation
• Limitations of Noisy Reversible Computation
• Experimental exploration of five-qubit quantum error correcting code with superconducting qubits
• Relative Entropy Convergence for Depolarizing Channels
• Simulating Noisy Quantum Circuits with Matrix Product Density Operators
• A Separation of Out-of-time-ordered Correlation and Entanglement
• On the modified logarithmic Sobolev inequality for the heat-bath dynamics for 1D systems
• The modified logarithmic Sobolev inequality for quantum spin systems: classical and commuting nearest neighbour interactions
• Neural network encoded variational quantum algorithms
• Entanglement Dynamics of Noisy Random Circuits
• Efficient sampling of noisy shallow circuits via monitored unraveling
• Entanglement rates for Renyi, Tsallis and other entropies
• A lower bound on the overhead of quantum error correction in low dimensions