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.

arXiv comment12 pages, 10 figures, close to published version

References in corpus (30)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Barren plateaus in quantum neural network training landscapes
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Approximate Optimization Algorithm
• An adaptive variational algorithm for exact molecular simulations on a quantum computer
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• Quantum optimization using variational algorithms on near-term quantum devices
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Accelerated Variational Quantum Eigensolver
• Improving Variational Quantum Optimization using CVaR
• Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
• Variational Quantum Eigensolver with Fewer Qubits
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• Capacity and quantum geometry of parametrized quantum circuits
• Benchmarking the Quantum Approximate Optimization Algorithm
• Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search
• Hybrid quantum-classical algorithms for approximate graph coloring
• How "Quantum" is the D-Wave Machine?
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem
• Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
• Adaptive pruning-based optimization of parameterized quantum circuits
• Finding spin-glass ground states using quantum walks
• Hybrid quantum-classical optimization for financial index tracking
• Improving the variational quantum eigensolver using variational adiabatic quantum computing
• Addressing hard classical problems with Adiabatically Assisted Variational Quantum Eigensolvers

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