Limitations of variational quantum algorithms: a quantum optimal transport approach

Abstract

The impressive progress in quantum hardware in the last years has raised the interest of the quantum computing community in harvesting the computational power of such devices. However, in the absence of error correction, these devices can only reliably implement very shallow circuits or comparatively deeper circuits at the expense of a nontrivial density of errors. In this work, we obtain extremely tight limitation bounds for standard NISQ proposals in both the noisy and noiseless regimes, with or without error-mitigation tools. The bounds limit the performance of both circuit model algorithms, such as QAOA, and also continuous-time algorithms, such as quantum annealing. In the noisy regime with local depolarizing noise $p$, we prove that at depths $L=\mathcal{O}(p^{-1})$ it is exponentially unlikely that the outcome of a noisy quantum circuit outperforms efficient classical algorithms for combinatorial optimization problems like Max-Cut. Although previous results already showed that classical algorithms outperform noisy quantum circuits at constant depth, these results only held for the expectation value of the output. Our results are based on newly developed quantum entropic and concentration inequalities, which constitute a homogeneous toolkit of theoretical methods from the quantum theory of optimal mass transport whose potential usefulness goes beyond the study of variational quantum algorithms.

arXiv commentClose to the published version

References in corpus (37)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Quantum computational advantage using photons
• Barren plateaus in quantum neural network training landscapes
• Noisy intermediate-scale quantum (NISQ) algorithms
• Error mitigation for short-depth quantum circuits
• Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
• On quantum Renyi entropies: a new generalization and some properties
• Roads towards fault-tolerant universal quantum computation
• Practical Quantum Error Mitigation for Near-Future Applications
• Hybrid quantum-classical algorithms and quantum error mitigation
• Strong converse for the classical capacity of entanglement-breaking and Hadamard channels via a sandwiched Renyi relative entropy
• Training variational quantum algorithms is NP-hard
• Lieb-Robinson Bounds and the Exponential Clustering Theorem
• Bounds for the adiabatic approximation with applications to quantum computation
• Quantum Error Correction: An Introductory Guide
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Error-mitigated digital quantum simulation
• Virtual Distillation for Quantum Error Mitigation
• Exponential Error Suppression for Near-Term Quantum Devices
• Quantum logarithmic Sobolev inequalities and rapid mixing
• The ${\chi }^2$-divergence and Mixing times of quantum Markov processes
• The Quantum Wasserstein Distance of Order 1
• Relative Entropy Bounds on Quantum, Private and Repeater Capacities
• Quasi-locality and efficient simulation of Markovian quantum dynamics
• Non-commutative calculus, optimal transport and functional inequalities in dissipative quantum systems
• Quantum optimal transport with quantum channels
• Hypercontractivity of quasi-free quantum semigroups
• Concentration bounds for quantum states with finite correlation length on quantum spin lattice systems
• On the local equivalence between the canonical and the microcanonical distributions for quantum spin systems
• Gaussian concentration bound and Ensemble equivalence in generic quantum many-body systems including long-range interaction
• Eigenstate thermalization from the clustering property of correlation
• Sandwiched Rényi Convergence for Quantum Evolutions

Cited by in corpus (4)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• On contraction coefficients, partial orders and approximation of capacities for quantum channels
• Conserved charges in the quantum simulation of integrable spin chains
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era