Benchmarking variational quantum algorithms for combinatorial optimization in practice
Top Cited Papers
Open Access
- 10 March 2026
- journal article
- research article
- Published by Springer Nature in Quantum Machine Intelligence
- Vol. 8 (1) , 26
Abstract
Variational quantum algorithms, and in particular variants of the variational quantum eigensolver, have been proposed as approaches to combinatorial optimization (CO) problems. With only shallow ansatz circuits, these methods are considered suitable for current noisy intermediate-scale quantum hardware. Yet, the resources required to train variational circuits often scale superpolynomially with problem size. In this study, we numerically investigate the practical implications of this scaling for CO problems, using Max-Cut and random QUBO instances as benchmarks. For a fixed computational budget, we compare the average performance of training shallow variational circuits, sampling with replacement, and greedy local search. We identify the minimum problem size at which the quantum algorithms consistently outperform random sampling, and for each size, we characterize their separation from greedy local search. Beyond average-case performance, we analyze correlations between algorithms across individual problem instances. These results strengthen the case for intuitive yet meaningful benchmarks of variational quantum algorithms for CO problems under realistic resource constraints.Keywords
All Related Versions
Funding Information
- Deutsches Elektronen-Synchrotron (DESY)
This publication has 47 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
- The Variational Quantum Eigensolver: A review of methods and best practicesPhysics Reports, 2022
- Charged particle tracking with quantum annealing optimizationQuantum Machine Intelligence, 2021
- Sustainable supply chain network design: An optimization-oriented reviewOmega, 2015
- The unconstrained binary quadratic programming problem: a surveyJournal of Combinatorial Optimization, 2014
- Combinatorial optimization and Green LogisticsAnnals of Operations Research, 2009
- Direct search algorithms for optimization calculationsActa Numerica, 1998
- Reducibility among Combinatorial Problems1972