Role of overparametrization in quantum approximate optimization

Abstract

Variational quantum algorithms have emerged as a cornerstone of contemporary quantum algorithms research. While they have demonstrated considerable promise in solving problems of practical interest, efficiently determining the minimal quantum resources necessary to obtain such a solution remains an open question. In this work, inspired by concepts from classical machine learning, we investigate the impact of overparameterization on the performance of variational algorithms. Our study focuses on the quantum approximate optimization algorithm (QAOA) -- a prominent variational quantum algorithm designed to solve combinatorial optimization problems. We investigate if circuit overparametrization is necessary and sufficient to solve such problems in QAOA, considering two representative problems -- MAX-CUT and MAX-2-SAT. For MAX-CUT we observe that overparametriation is both sufficient and (statistically) necessary for attaining exact solutions, as confirmed numerically for up to $20$ qubits. In fact, for MAX-CUT on 2-regular graphs we show the necessity to be exact, based on the analytically found optimal depth. In sharp contrast, for MAX-2-SAT, underparametrized circuits suffice to solve most instances. This result highlights the potential of QAOA in the underparametrized regime, supporting its utility for current noisy devices.

Minor typos corrected

References in corpus (49)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• The theory of variational hybrid quantum-classical algorithms
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum machine learning in feature Hilbert spaces
• Reconciling modern machine learning practice and the bias-variance trade-off
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Quantum annealing with more than one hundred qubits
• Quantum Fisher information matrix and multiparameter estimation
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Natural Gradient
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Two-qubit silicon quantum processor with operation fidelity exceeding 99%
• Reinforcement Learning in Different Phases of Quantum Control
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• A Geometric Perspective on Quantum Parameter Estimation
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Barren Plateaus in Variational Quantum Computing
• Variational Quantum Linear Solver
• $XY$-mixers: analytical and numerical results for QAOA
• Theory of overparametrization in quantum neural networks
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer
• Reachability Deficits in Quantum Approximate Optimization
• Optimal Protocols in Quantum Annealing and QAOA Problems
• Parameter Concentration in Quantum Approximate Optimization
• Counterdiabaticity and the quantum approximate optimization algorithm
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Universal Variational Quantum Computation
• Evaluating the noise resilience of variational quantum algorithms
• On the Universality of the Quantum Approximate Optimization Algorithm
• Supervised learning with a quantum classifier using a multi-level system
• How many qubits are needed for quantum computational supremacy?
• Universal Effectiveness of High-Depth Circuits in Variational Eigenproblems
• Training Saturation in Layerwise Quantum Approximate Optimisation
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Scaling Trapped Ion Quantum Computers Using Fast Gates and Microtraps
• On Circuit Depth Scaling For Quantum Approximate Optimization
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
• Towards the speed limit of high fidelity 2-qubit gates
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Robustness of Variational Quantum Algorithms against stochastic parameter perturbation
• Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size
• Progress towards analytically optimal angles in quantum approximate optimisation
• Laziness, Barren Plateau, and Noise in Machine Learning
• Quantum Natural Gradient optimizer on noisy platforms: QAOA as a case study
• Mitigating Quantum Gate Errors for Variational Eigensolvers Using Hardware-Inspired Zero-Noise Extrapolation
• Expressivity Limits in Quantum Walk-based Optimization