Progress toward favorable landscapes in quantum combinatorial optimization

Abstract

The performance of variational quantum algorithms relies on the success of using quantum and classical computing resources in tandem. Here, we study how these quantum and classical components interrelate. In particular, we focus on algorithms for solving the combinatorial optimization problem MaxCut, and study how the structure of the classical optimization landscape relates to the quantum circuit used to evaluate the MaxCut objective function. In order to analytically characterize the impact of quantum features on the critical points of the landscape, we consider a family of quantum circuit ansätze composed of mutually commuting elements. We identify multiqubit operations as a key resource and show that overparameterization allows for obtaining favorable landscapes. Namely, we prove that an ansatz from this family containing exponentially many variational parameters yields a landscape free of local optima for generic graphs. However, we further prove that these ansätze do not offer superpolynomial advantages over purely classical MaxCut algorithms. We then present a series of numerical experiments illustrating that noncommutativity and entanglement are important features for improving algorithm performance.

arXiv admin note: text overlap with arXiv:2105.05365

References in corpus (9)

• A Quantum Approximate Optimization Algorithm
• Non-convex Optimization for Machine Learning
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• Capacity and quantum geometry of parametrized quantum circuits
• First-order Methods Almost Always Avoid Saddle Points
• The Power of Normalization: Faster Evasion of Saddle Points
• Feedback-based quantum optimization
• Learning Unitaries by Gradient Descent
• Low-depth Quantum State Preparation

Cited by in corpus (26)

• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Barren Plateaus in Variational Quantum Computing
• Theory of overparametrization in quantum neural networks
• Group-Invariant Quantum Machine Learning
• A Lie Algebraic Theory of Barren Plateaus for Deep Parameterized Quantum Circuits
• Does provable absence of barren plateaus imply classical simulability?
• On the practical usefulness of the Hardware Efficient Ansatz
• Quantum-Informed Recursive Optimization Algorithms
• Lyapunov control-inspired strategies for quantum combinatorial optimization
• An entanglement perspective on the quantum approximate optimization algorithm
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Effects of noise on the overparametrization of quantum neural networks
• Squeezing and quantum approximate optimization
• Quantum Energy Landscape and VQA Optimization
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Quantum Chaos and Circuit Parameter Optimization
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Variational quantum computing for quantum simulation: principles, implementations, and challenges
• Quantum optimal control in quantum technologies. Strategic report on current status, visions and goals for research in Europe
• Backpropagation scaling in parameterised quantum circuits
• Ising Hamiltonians for Constrained Combinatorial Optimization Problems and the Metropolis-Hastings Warm-Starting Algorithm
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Deep-Circuit QAOA
• Optimal solutions to quantum annealing using two independent control functions
• Adiabatic quantum computing with parameterized quantum circuits
• Variational Quantum Algorithm Landscape Reconstruction by Low-Rank Tensor Completion