Quantum variational optimization: The role of entanglement and problem hardness

Abstract

Quantum variational optimization has been posed as an alternative to solve optimization problems faster and at a larger scale than what classical methods allow. In this paper we study systematically the role of entanglement, the structure of the variational quantum circuit, and the structure of the optimization problem, in the success and efficiency of these algorithms. For this purpose, our study focuses on the variational quantum eigensolver (VQE) algorithm, as applied to quadratic unconstrained binary optimization (QUBO) problems on random graphs with tunable density. Our numerical results indicate an advantage in adapting the distribution of entangling gates to the problem's topology, specially for problems defined on low-dimensional graphs. Furthermore, we find evidence that applying conditional value at risk type cost functions improves the optimization, increasing the probability of overlap with the optimal solutions. However, these techniques also improve the performance of Ansätze based on product states (no entanglement), suggesting that a new classical optimization method based on these could outperform existing NISQ architectures in certain regimes. Finally, our study also reveals a correlation between the hardness of a problem and the Hamming distance between the ground- and first-excited state, an idea that can be used to engineer benchmarks and understand the performance bottlenecks of optimization methods.

12 pages, 10 figures, close to published version

References in corpus (6)

• Variational Quantum Algorithms
• A Quantum Approximate Optimization Algorithm
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Capacity and quantum geometry of parametrized quantum circuits
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• Improving the variational quantum eigensolver using variational adiabatic quantum computing

Cited by in corpus (20)

• Filtering variational quantum algorithms for combinatorial optimization
• Challenges of variational quantum optimization with measurement shot noise
• Evaluation of Parameterized Quantum Circuits with Cross-Resonance Pulse-Driven Entanglers
• Calibrating the role of entanglement in variational quantum circuits
• Practical Verification of Quantum Properties in Quantum Approximate Optimization Runs
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management
• Low-depth Clifford circuits approximately solve MaxCut
• Random coordinate descent: a simple alternative for optimizing parameterized quantum circuits
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Post-processing variationally scheduled quantum algorithm for constrained combinatorial optimization problems
• Genuine Multipartite Entanglement in Quantum Optimization
• Machine-Learning Insights into the Entanglement-trainability Correlation of Parameterized Quantum Circuits
• Single entanglement connection architecture between multi-layer bipartite Hardware Efficient Ansatz
• Information scrambling and entanglement in quantum approximate optimization algorithm circuits
• Accelerating Feedback-Based Quantum Algorithms through Time Rescaling
• Crosstalk-Based Parameterized Quantum Circuit Approximation
• Warm Start of Variational Quantum Algorithms for Quadratic Unconstrained Binary Optimization Problems
• A method for quantifying the generalization capabilities of generative models for solving Ising models
• Adiabatic Dynamics of Entanglement