Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice
Authors:
Preprint
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.Keywords
All Related Versions
This publication has 35 references indexed in Scilit:
- A review on Quantum Approximate Optimization Algorithm and its variantsPhysics Reports, 2024
- Charged Particle Reconstruction for Future High Energy Colliders with Quantum Approximate Optimization Algorithm2024
- Quantum Algorithms for Charged Particle Track Reconstruction in the LUXE ExperimentComputing and Software for Big Science, 2023
- Quantum variational algorithms are swamped with trapsNature Communications, 2022
- Charged particle tracking with quantum annealing optimizationQuantum Machine Intelligence, 2021
- Sustainable supply chain network design: An optimization-oriented reviewOmega, 2015
- A variational eigenvalue solver on a photonic quantum processorNature Communications, 2014
- Combinatorial optimization and Green LogisticsAnnals of Operations Research, 2009
- Direct search algorithms for optimization calculationsActa Numerica, 1998
- Reducibility among Combinatorial Problems1972