Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice

Abstract

Variational quantum algorithms and, in particular, variants of the varational quantum eigensolver have been proposed to address combinatorial optimization (CO) problems. Using only shallow ansatz circuits, these approaches are deemed suitable for current noisy intermediate-scale quantum hardware. However, the resources required for training shallow variational quantum circuits often scale superpolynomially in problem size. In this study we numerically investigate what this scaling result means in practice for solving CO problems using Max-Cut as a benchmark. For fixed resources, we compare the average performance of training a shallow variational quantum circuit, sampling with replacement, and a greedy algorithm starting from the same initial point as the quantum algorithm. We identify a minimum problem size for which the quantum algorithm can consistently outperform sampling and, for each problem size, characterize the separation between the quantum algorithm and the greedy algorithm. Furthermore, we extend the average case analysis by investigating the correlation between the performance of the algorithms by instance. Our results provide a step towards meaningful benchmarks of variational quantum algorithms for CO problems for a realistic set of resources.

References in corpus (28)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Array Programming with NumPy
• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• The Variational Quantum Eigensolver: a review of methods and best practices
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Improving Variational Quantum Optimization using CVaR
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Quantum computing with Qiskit
• Equivalence of quantum barren plateaus to cost concentration and narrow gorges
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• 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
• Robust resource-efficient quantum variational ansatz through evolutionary algorithm
• Image Acquisition Planning for Earth Observation Satellites with a Quantum Annealer
• Can Error Mitigation Improve Trainability of Noisy Variational Quantum Algorithms?
• Challenges of variational quantum optimization with measurement shot noise
• Towards large-scale quantum optimization solvers with few qubits
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• QAOA Performance in Noisy Devices: The Effect of Classical Optimizers and Ansatz Depth
• Charged particle tracking with quantum annealing-inspired optimization
• Towards Finding an Optimal Flight Gate Assignment on a Digital Quantum Computer
• Studying quantum algorithms for particle track reconstruction in the LUXE experiment
• Equivalence of cost concentration and gradient vanishing for quantum circuits: An elementary proof in the Riemannian formulation
• Charged particle reconstruction for future high energy colliders with Quantum Approximate Optimization Algorithm
• Investigating Techniques to Optimise the Layout of Turbines in a Windfarm using a Quantum Computer
• Performance analysis of a filtering variational quantum algorithm
• Warm Start of Variational Quantum Algorithms for Quadratic Unconstrained Binary Optimization Problems