Performance of hybrid quantum/classical variational heuristics for combinatorial optimization

Abstract

The recent literature on near-term applications for quantum computers contains several examples of the applications of hybrid quantum/classical variational approaches. This methodology can be applied to a variety of optimization problems, but its practical performance is not well studied yet. This paper moves some steps in the direction of characterizing the practical performance of the methodology, in the context of finding solutions to classical combinatorial optimization problems. Our study is based on numerical results obtained applying several classical nonlinear optimization algorithms to Hamiltonians for six combinatorial optimization problems; the experiments are conducted via noise-free classical simulation of the quantum circuits implemented in Qiskit. We empirically verify that: (1) finding the ground state is harder for Hamiltonians with many Pauli terms; (2) classical global optimization methods are more successful than local methods due to their ability of avoiding the numerous local optima; (3) there does not seem to be a clear advantage in introducing entanglement in the variational form.

Additional experiments to quantify the effect of entanglement, or lack thereof

References in corpus (2)

• Quantum optimization using variational algorithms on near-term quantum devices
• qTorch: The Quantum Tensor Contraction Handler

Cited by in corpus (60)

• Quantum Computing for Finance: State of the Art and Future Prospects
• Layerwise learning for quantum neural networks
• Improving Variational Quantum Optimization using CVaR
• Grover Adaptive Search for Constrained Polynomial Binary Optimization
• Digitized-counterdiabatic quantum approximate optimization algorithm
• Hybrid quantum neural network for drug response prediction
• A Comparison of Various Classical Optimizers for a Variational Quantum Linear Solver
• Quantum Machine Learning: from physics to software engineering
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• A case study of variational quantum algorithms for a job shop scheduling problem
• Minimizing State Preparations in Variational Quantum Eigensolver by Partitioning into Commuting Families
• Variational Quantum Eigensolver for Frustrated Quantum Systems
• Using models to improve optimizers for variational quantum algorithms
• QuASeR -- Quantum Accelerated De Novo DNA Sequence Reconstruction
• Multilevel Combinatorial Optimization Across Quantum Architectures
• Quantum Algorithms for Mixed Binary Optimization applied to Transaction Settlement
• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
• Quantum variational optimization: The role of entanglement and problem hardness
• Low depth mechanisms for quantum optimization
• Solving hadron structures using the basis light-front quantization approach on quantum computers
• Evaluating Quantum Approximate Optimization Algorithm: A Case Study
• Challenges of variational quantum optimization with measurement shot noise
• Hybrid quantum image classification and federated learning for hepatic steatosis diagnosis
• Quantum Approximate Optimization Algorithm pseudo-Boltzmann states
• Hybrid quantum-classical optimization for financial index tracking
• Improving the variational quantum eigensolver using variational adiabatic quantum computing
• An evolving objective function for improved variational quantum optimisation
• An introduction to variational quantum algorithms for combinatorial optimization problems
• Focusing on the Hybrid Quantum Computing -- Tabu Search Algorithm: new results on the Asymmetric Salesman Problem
• Avoiding local minima in Variational Quantum Algorithms with Neural Networks
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management
• Towards Finding an Optimal Flight Gate Assignment on a Digital Quantum Computer
• Quantum Generative Models for Small Molecule Drug Discovery
• Variational quantum eigensolver with linear depth problem-inspired ansatz for solving portfolio optimization in finance
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Mixed Integer Linear Programming Solver Using Benders Decomposition Assisted by Neutral Atom Quantum Processor
• Natural orbitals and sparsity of quantum mutual information
• Algorithm-Oriented Qubit Mapping for Variational Quantum Algorithms
• Approaching Collateral Optimization for NISQ and Quantum-Inspired Computing
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Random Natural Gradient
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Max-cut Clustering Utilizing Warm-Start QAOA and IBM Runtime
• A Classically Efficient Quantum Scalable Fermi-Hubbard Benchmark
• Hybrid Quantum Neural Networks with Variational Quantum Regressor for Enhancing QSPR Modeling of CO2-Capturing Amine
• Connection between single-layer Quantum Approximate Optimization Algorithm interferometry and thermal distributions sampling
• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• Single entanglement connection architecture between multi-layer bipartite Hardware Efficient Ansatz
• Utility of NISQ devices: optimizing experimental parameters for the fabrication of Au atomic junction using gate-based quantum computers
• Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice
• Adiabatic quantum computing with parameterized quantum circuits
• Warm Start of Variational Quantum Algorithms for Quadratic Unconstrained Binary Optimization Problems
• Optimal Quantum Likelihood Estimation
• Improving the Quantum Approximate Optimization Algorithm with postselection
• Improving the trainability of VQE on NISQ computers for solving portfolio optimization using convex interpolation
• Gaussian Boson Sampling for binary optimization
• Hybrid Quantum-Classical Multi-cut Benders Approach with a Power System Application
• Topological and geometric patterns in optimal bang-bang protocols for variational quantum algorithms: application to the $XXZ$ model on the square lattice
• Enhancing the Performance of Quantum Neutral-Atom-Assisted Benders Decomposition
• Quantum-Classical Computing for Time-Dependent Ion-Atom Collision Dynamics: Applications to Charge Transfer Cross Section Simulations