Scalability Challenges in Variational Quantum Optimization under Stochastic Noise

Abstract

With rapid advances in quantum hardware, a central question is whether quantum devices with or without full error correction can outperform classical computers on practically relevant problems. Variational Quantum Algorithms (VQAs) have gained significant attention as promising candidates in this pursuit, particularly for combinatorial optimization problems. While reports of their challenges and limitations continue to accumulate, many studies remain optimistic based on small-scale, idealized testing setups, leaving doubt about the scalability of VQAs for large-scale problems. We systematically investigate this scaling behavior by analyzing how classical optimizers minimize variational quantum loss functions for random QUBO instances in the presence of uncertainty, modeled as effective Gaussian noise. We find that the critical noise threshold for successful optimization decreases rapidly as system size grows. This decline exceeds what can be explained solely by shrinking loss variance, confirming deeper, fundamental limitations in the loss landscapes of VQAs beyond barren plateaus. Translating these thresholds into required measurement shots reveals that achieving sufficient precision in the evaluated loss values quickly becomes impractical, even for moderately-sized problems. Our findings demonstrate serious scalability challenges for VQAs in optimization stemming from mere uncertainty, indicating potential barriers to achieving practical quantum advantage with current hybrid approaches.

25 pages, 16 figures, 3 tables

References in corpus (55)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Variational Quantum Algorithms
• Quantum computational advantage using photons
• Noisy intermediate-scale quantum (NISQ) algorithms
• Trapped-Ion Quantum Computing: Progress and Challenges
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Evaluating analytic gradients on quantum hardware
• The Variational Quantum Eigensolver: a review of methods and best practices
• Training variational quantum algorithms is NP-hard
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• An initialization strategy for addressing barren plateaus in parametrized quantum circuits
• Warm-starting quantum optimization
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• The Bitter Truth About Quantum Algorithms in the NISQ Era
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Barren Plateaus in Variational Quantum Computing
• Sequential minimal optimization for quantum-classical hybrid algorithms
• Challenges and Opportunities in Quantum Optimization
• Theory of overparametrization in quantum neural networks
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Reachability Deficits in Quantum Approximate Optimization
• Large gradients via correlation in random parameterized quantum circuits
• A Lie Algebraic Theory of Barren Plateaus for Deep Parameterized Quantum Circuits
• Performance comparison of optimization methods on variational quantum algorithms
• Classical Optimizers for Noisy Intermediate-Scale Quantum Devices
• A Comparison of Various Classical Optimizers for a Variational Quantum Linear Solver
• Evaluating the noise resilience of variational quantum algorithms
• Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
• Using models to improve optimizers for variational quantum algorithms
• The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansätze
• Classical algorithms for quantum mean values
• Benchmarking of Different Optimizers in the Variational Quantum Algorithms for Applications in Quantum Chemistry
• Graph neural network initialisation of quantum approximate optimisation
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Error propagation in NISQ devices for solving classical optimization problems
• Can Error Mitigation Improve Trainability of Noisy Variational Quantum Algorithms?
• Towards large-scale quantum optimization solvers with few qubits
• Challenges of variational quantum optimization with measurement shot noise
• Trainability Enhancement of Parameterized Quantum Circuits via Reduced-Domain Parameter Initialization
• QAOA Performance in Noisy Devices: The Effect of Classical Optimizers and Ansatz Depth
• Quantum utility -- definition and assessment of a practical quantum advantage
• Non-trivial symmetries in quantum landscapes and their resilience to quantum noise
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
• Classification of dynamical Lie algebras for translation-invariant 2-local spin systems in one dimension
• Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem
• Stochastic noise can be helpful for variational quantum algorithms
• Quantum Energy Landscape and VQA Optimization
• A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
• Trainability Barriers in Low-Depth QAOA Landscapes
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Efficient Encodings of the Travelling Salesperson Problem for Variational Quantum Algorithms
• Variational Quantum Non-Orthogonal Optimization
• Iteration Complexity of Variational Quantum Algorithms
• A coherent approach to quantum-classical optimization

Cited by in corpus (1)

• Inference of maximum parsimony phylogenetic trees with model-based classical and quantum methods