Progress toward favorable landscapes in quantum combinatorial optimization
arXiv:2105.01114 · doi:10.1103/PhysRevA.104.032401
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 commentarXiv admin note: text overlap with arXiv:2105.05365
References in corpus (48)
- Quantum Computing in the NISQ era and beyond
- A variational eigenvalue solver on a quantum processor
- Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
- Ising formulations of many NP problems
- Barren plateaus in quantum neural network training landscapes
- The theory of variational hybrid quantum-classical algorithms
- A Quantum Approximate Optimization Algorithm
- Error mitigation for short-depth quantum circuits
- Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
- An adaptive variational algorithm for exact molecular simulations on a quantum computer
- Circuit-centric quantum classifiers
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Efficient variational quantum simulator incorporating active error minimisation
- Quantum optimization using variational algorithms on near-term quantum devices
- Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
- Practical Quantum Error Mitigation for Near-Future Applications
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- Quantum Natural Gradient
- qubit-ADAPT-VQE: An adaptive algorithm for constructing hardware-efficient ansatze on a quantum processor
- Non-convex Optimization for Machine Learning
- Hybrid Quantum-Classical Approach to Quantum Optimal Control
- Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
- Low-cost error mitigation by symmetry verification
- Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
- Unsupervised Machine Learning on a Hybrid Quantum Computer
- Variational Quantum Linear Solver
- Instantaneous Quantum Computation
- Quantum Control Landscapes
- Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer
- Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
- Quantum computers as universal quantum simulators: state-of-art and perspectives
- Capacity and quantum geometry of parametrized quantum circuits
- Benchmarking the Quantum Approximate Optimization Algorithm
- Implementation of the XY interaction family with calibration of a single pulse
- From pulses to circuits and back again: A quantum optimal control perspective on variational quantum algorithms
- Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
- First-order Methods Almost Always Avoid Saddle Points
- Sampling-based Learning Control for Quantum Systems with Uncertainties
- The Power of Normalization: Faster Evasion of Saddle Points
- Feedback-based quantum optimization
- Mutual information-assisted Adaptive Variational Quantum Eigensolver
- Quantum Commuting Circuits and Complexity of Ising Partition Functions
- Low depth mechanisms for quantum optimization
- Learning Unitaries by Gradient Descent
- Assessing three closed-loop learning algorithms by searching for high-quality quantum control pulses
- Combining the synergistic control capabilities of modelling and experiments: illustration of finding a minimum time quantum objective
- Drawing together control landscape and tomography principles
- 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