pith. sign in

arxiv: 2408.03073 · v1 · submitted 2024-08-06 · 🪐 quant-ph

Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice

Tim Schw\"agerl , Yahui Chai , Tobias Hartung , Karl Jansen , Stefan K\"uhn This is my paper

Pith reviewed 2026-05-23 22:30 UTC · model grok-4.3

classification 🪐 quant-ph
keywords variational quantum algorithmscombinatorial optimizationMax-Cutbenchmarkingshallow ansatznumerical simulationperformance comparison
0
0 comments X

The pith

Shallow variational quantum algorithms for Max-Cut outperform sampling only beyond a minimum problem size under fixed resources.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper numerically compares training a shallow variational quantum circuit against sampling with replacement and a greedy algorithm on Max-Cut instances, all starting from the same point and using fixed resources. It identifies the smallest problem size at which the quantum method consistently beats sampling and measures the performance gap to the greedy baseline for every size. The study also tracks whether strong or weak performance on one instance predicts similar behavior on others. These comparisons matter because they translate the known superpolynomial training cost into concrete statements about when variational quantum methods could become useful for combinatorial optimization on near-term hardware.

Core claim

Numerical simulations with fixed resources show that a shallow variational quantum algorithm on Max-Cut instances begins to outperform sampling with replacement above a minimum problem size; for each size the separation from the greedy algorithm is characterized, and instance-wise correlations in performance across the three methods are quantified.

What carries the argument

Average-case and instance-correlated performance comparison of shallow variational quantum circuit training versus sampling with replacement versus greedy search on Max-Cut problems under identical resource limits and starting points.

If this is right

  • Above the identified minimum size, variational quantum methods deliver a measurable edge over pure sampling for the same computational budget.
  • The quantified gap to greedy shows the regime in which the quantum approach could compete with established classical heuristics.
  • Instance-wise correlations indicate that performance on one problem instance can be used to anticipate results on related instances.
  • The benchmarks translate abstract scaling results into concrete guidance on resource requirements for practical use.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Extending the comparison to larger problem sizes or different ansatz depths could reveal whether the minimum-size threshold shifts or saturates.
  • The instance-correlation result suggests a possible hybrid workflow in which classical pre-screening selects instances likely to benefit from quantum training.
  • If the same separation pattern appears on other combinatorial problems, the minimum-size finding may generalize beyond Max-Cut.

Load-bearing premise

Numerical simulations that use fixed resources and chosen shallow ansatzes accurately reflect the practical performance of variational quantum algorithms on combinatorial optimization problems without extra hardware noise or connectivity constraints.

What would settle it

Running the same Max-Cut instances on actual quantum hardware and finding that the variational circuit never outperforms sampling even at the sizes identified in simulation would falsify the reported minimum-size threshold.

Figures

Figures reproduced from arXiv: 2408.03073 by Karl Jansen, Stefan K\"uhn, Tim Schw\"agerl, Tobias Hartung, Yahui Chai.

Figure 1
Figure 1. Figure 1: FIG. 1: The circuit structure of the VQE for 5 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2: Frequently used performance metrics for VQAs [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3: Average difference in performance metrics of [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5: Average difference in approximation ratio (blue [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6: Mean and standard deviation of the [PITH_FULL_IMAGE:figures/full_fig_p009_6.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript numerically benchmarks shallow variational quantum algorithms (VQAs) for Max-Cut combinatorial optimization by comparing, under fixed circuit resources and noiseless simulations, the average performance of VQA training against random sampling with replacement and a greedy algorithm started from the same initial point. It reports identification of a minimum problem size at which the VQA consistently outperforms sampling, characterization of the performance separation from the greedy algorithm at each size, and an extension to instance-wise performance correlations. The work is framed as providing practical benchmarks relevant to NISQ hardware.

Significance. If the numerical thresholds and separations prove robust, the study supplies concrete empirical data on when shallow VQAs may offer advantages over elementary classical methods for CO problems at fixed resources, moving beyond abstract scaling arguments. The instance-correlation analysis is a strength that adds nuance to average-case comparisons. The absence of noise modeling, however, restricts the direct applicability of the reported minimum sizes and separations to actual hardware.

major comments (2)
  1. [Introduction and Results] Introduction (motivation paragraph on NISQ suitability) and Results (performance comparison sections): the central claim of identifying a 'minimum problem size' for consistent outperformance 'in practice' and 'for a realistic set of resources' rests on noiseless ideal unitary simulations; because the abstract positions the benchmarks as relevant to current hardware, the omission of decoherence, readout errors, and connectivity constraints is load-bearing and could shift the reported thresholds.
  2. [Methods and Results] Methods/Results (numerical protocol): the determination of the minimum problem size where VQA 'consistently outperforms sampling' does not specify the number of Max-Cut instances, random seeds, statistical tests, or data-selection criteria used to establish consistency; without these, the threshold identification cannot be assessed for robustness against post-hoc choices or insufficient sampling.
minor comments (2)
  1. [Abstract] Abstract: 'varational' appears twice and should be corrected to 'variational'.
  2. [Abstract] Abstract: the statement that training resources 'often scale superpolynomially' would benefit from an explicit citation to the referenced scaling result.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive feedback. We address the two major comments point by point below, indicating where revisions will strengthen the manuscript while preserving its core contributions on ideal-case benchmarks.

read point-by-point responses

  1. Referee: [Introduction and Results] Introduction (motivation paragraph on NISQ suitability) and Results (performance comparison sections): the central claim of identifying a 'minimum problem size' for consistent outperformance 'in practice' and 'for a realistic set of resources' rests on noiseless ideal unitary simulations; because the abstract positions the benchmarks as relevant to current hardware, the omission of decoherence, readout errors, and connectivity constraints is load-bearing and could shift the reported thresholds.

    Authors: We agree that all reported results are obtained from noiseless ideal unitary simulations and that this is a genuine limitation for direct claims about NISQ hardware. The manuscript deliberately isolates the effect of fixed circuit resources in the ideal case to establish a baseline; including realistic noise would introduce additional modeling choices (error rates, connectivity graphs) that lie outside the present scope. We will revise the abstract and the motivation paragraph in the introduction to state explicitly that the thresholds and separations apply to the noiseless setting and to note that decoherence and connectivity constraints may alter the observed minimum sizes. This is a partial revision: the numerical protocol and results themselves remain unchanged. revision: partial

  2. Referee: [Methods and Results] Methods/Results (numerical protocol): the determination of the minimum problem size where VQA 'consistently outperforms sampling' does not specify the number of Max-Cut instances, random seeds, statistical tests, or data-selection criteria used to establish consistency; without these, the threshold identification cannot be assessed for robustness against post-hoc choices or insufficient sampling.

    Authors: The referee is correct that the current text does not provide a consolidated description of the statistical protocol. We will add a dedicated subsection in Methods that states the exact numbers of Max-Cut instances per problem size, the number of random seeds per instance, the precise criterion used to declare 'consistent outperformance,' and any statistical measures employed. This addition will allow readers to evaluate robustness directly and removes any ambiguity about post-hoc selection. revision: yes

Circularity Check

0 steps flagged

No circularity: purely empirical numerical benchmarking with independent performance metrics.

full rationale

The paper conducts numerical simulations comparing VQA training, sampling, and greedy algorithms on Max-Cut instances for fixed resources. It reports observed performance thresholds and instance correlations directly from these computations. No derivations, first-principles predictions, fitted parameters renamed as predictions, or self-citation chains are present in the abstract or described methodology. All metrics (outperformance thresholds, separations) are defined and measured independently of any internal fitting that would make results tautological. This matches the default case of a self-contained empirical study.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review reveals no explicit free parameters, axioms, or invented entities; the work is an empirical comparison study.

pith-pipeline@v0.9.0 · 5722 in / 1101 out tokens · 24955 ms · 2026-05-23T22:30:32.333470+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages · 4 internal anchors

  1. [1]

    Eskandarpour, P

    M. Eskandarpour, P. Dejax, J. Miemczyk, and O. P´ eton, Sustainable supply chain network design: An optimization-oriented review, Omega 54, 11 (2015)

    work page 2015

  2. [2]

    Sbihi and R

    A. Sbihi and R. Eglese, Combinatorial optimization and green logistics, Annals of Operations Research 175, 254 (2010)

    work page 2010

  3. [3]

    Barahona, M

    F. Barahona, M. Gr¨ otschel, M. J¨ unger, and G. Reinelt, An Application of Combinatorial Optimization to Sta- tistical Physics and Circuit Layout Design, Operations Research 36, 493 (1988)

    work page 1988

  4. [4]

    Saito, P

    M. Saito, P. Calafiura, H. Gray, W. Lavrijsen, L. Lin- der, Y. Okumura, R. Sawada, A. Smith, J. Tanaka, and K. Terashi, Quantum annealing algorithms for track pat- tern recognition, EPJ Web of Conferences 245, 10006 (2020)

    work page 2020

  5. [5]

    H. M. Gray, Quantum pattern recognition algorithms for charged particle tracking, Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engi- neering Sciences 380, 10.1098/rsta.2021.0103 (2021)

    work page doi:10.1098/rsta.2021.0103 2021

  6. [6]

    Zlokapa, A

    A. Zlokapa, A. Anand, J.-R. Vlimant, J. M. Duarte, J. Job, D. Lidar, and M. Spiropulu, Charged particle tracking with quantum annealing optimization, Quan- tum Machine Intelligence 3, 10.1007/s42484-021-00054-w (2021)

    work page doi:10.1007/s42484-021-00054-w 2021

  7. [7]

    Funcke, T

    L. Funcke, T. Hartung, B. Heinemann, K. Jansen, A. Kropf, S. K¨ uhn, F. Meloni, D. Spataro, C. T¨ uys¨ uz, and Y. C. Yap, Studying quantum algorithms for particle track reconstruction in the LUXE experiment, Journal of Physics: Conference Series 2438, 012127 (2023)

    work page 2023

  8. [8]

    Schw¨ agerl, C

    T. Schw¨ agerl, C. Issever, K. Jansen, T. J. Khoo, S. K¨ uhn, C. T¨ uys¨ uz, and H. Weber,Particle track reconstruction with noisy intermediate-scale quantum computers , Tech. Rep. (2023) arXiv:2303.13249

    work page arXiv 2023

  9. [9]

    Crippa, L

    A. Crippa, L. Funcke, T. Hartung, B. Heinemann, K. Jansen, A. Kropf, S. K¨ uhn, F. Meloni, D. Spataro, C. T¨ uys¨ uz, and Y. C. Yap, Quantum algorithms for charged particle track reconstruction in the luxe exper- iment, Computing and Software for Big Science 7, 14 (2023)

    work page 2023

  10. [10]

    Okawa, Charged particle reconstruction for future high energy colliders with Quantum Approximate Optimiza- tion Algorithm , Tech

    H. Okawa, Charged particle reconstruction for future high energy colliders with Quantum Approximate Optimiza- tion Algorithm , Tech. Rep. (2023) arXiv:2310.10255

    work page arXiv 2023

  11. [11]

    R. M. Karp, Reducibility among combinatorial prob- lems, in Complexity of Computer Computations: Pro- ceedings of a symposium on the Complexity of Com- puter Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corp...

    work page 1972

  12. [12]

    Shor, Algorithms for quantum computation: discrete logarithms and factoring, in Proceedings 35th Annual Symposium on Foundations of Computer Science (1994) pp

    P. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in Proceedings 35th Annual Symposium on Foundations of Computer Science (1994) pp. 124–134

    work page 1994

  13. [13]

    L. K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the Twenty-Eighth An- nual ACM Symposium on Theory of Computing , STOC ’96 (Association for Computing Machinery, New York, NY, USA, 1996) p. 212–219

    work page 1996

  14. [14]

    Quantum Computing in the NISQ era and beyond

    J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018), arXiv:1801.00862

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  15. [15]

    A Quantum Approximate Optimization Algorithm

    E. Farhi, J. Goldstone, and S. Gutmann, A Quantum Approximate Optimization Algorithm , Tech. Rep. (2014) arXiv:1411.4028. 11

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  16. [16]

    Peruzzo, J

    A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, A variational eigenvalue solver on a photonic quantum processor, Nature Communications 5, 4213 (2014)

    work page 2014

  17. [17]

    Blekos, D

    K. Blekos, D. Brand, A. Ceschini, C.-H. Chou, R.-H. Li, K. Pandya, and A. Summer, A Review on Quantum Approximate Optimization Algorithm and its Variants, Physics Reports 1068, 1 (2024), arXiv:2306.09198

    work page arXiv 2024

  18. [18]

    Mohammadbagherpoor, P

    H. Mohammadbagherpoor, P. Dreher, M. Ibrahim, Y.- H. Oh, J. Hall, R. E. Stone, and M. Stojkovic, Exploring airline gate-scheduling optimization using quantum com- puters, arXiv:2111.09472 (2021)

    work page arXiv 2021

  19. [19]

    Stollenwerk, V

    T. Stollenwerk, V. Michaud, E. Lobe, M. Picard, A. Basermann, and T. Botter, Agile earth observa- tion satellite scheduling with a quantum annealer, IEEE Transactions on Aerospace and Electronic Systems 57, 3520 (2021)

    work page 2021

  20. [20]

    Y. Chai, L. Funcke, T. Hartung, K. Jansen, S. K¨ uhn, P. Stornati, and T. Stollenwerk, Towards Finding an Optimal Flight Gate Assignment on a Digital Quantum Computer, Physical Review Applied 20, 064025 (2023), arXiv:2302.11595

    work page arXiv 2023

  21. [21]

    Y. Chai, E. Epifanovsky, K. Jansen, A. Kaushik, and S. K¨ uhn,Simulating the flight gate assignment problem on a trapped ion quantum computer , Tech. Rep. (2023) arXiv:2309.09686

    work page arXiv 2023

  22. [22]

    Hancock, M

    J. Hancock, M. J. Craven, C. McNeile, and D. Vadacchino, Investigating techniques to optimise the layout of turbines in a windfarm using a quantum computer, Tech. Rep. (2023) arXiv:2312.13123

    work page arXiv 2023

  23. [23]

    Amaro, M

    D. Amaro, M. Rosenkranz, N. Fitzpatrick, K. Hirano, and M. Fiorentini, A case study of variational quantum algorithms for a job shop scheduling problem, EPJ Quan- tum Technology 9, 1 (2022)

    work page 2022

  24. [24]

    Performance of hybrid quantum/classical variational heuristics for combinatorial optimization

    G. Nannicini, Performance of hybrid quantum/classical variational heuristics for combinatorial optimization, Physical Review E 99, 013304 (2019), arXiv:1805.12037

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  25. [25]

    Arrasmith, Z

    A. Arrasmith, Z. Holmes, M. Cerezo, and P. J. Coles, Equivalence of quantum barren plateaus to cost concen- tration and narrow gorges, Quantum Science and Tech- nology 7, 045015 (2022), arXiv:2104.05868

    work page arXiv 2022

  26. [26]

    E. R. Anschuetz and B. T. Kiani, Quantum variational algorithms are swamped with traps, Nature Communica- tions 13, 7760 (2022)

    work page 2022

  27. [27]

    Amaro, C

    D. Amaro, C. Modica, M. Rosenkranz, M. Fioren- tini, M. Benedetti, and M. Lubasch, Filtering varia- tional quantum algorithms for combinatorial optimiza- tion, Quantum Science and Technology 7, 015021 (2022), arXiv:2106.10055

    work page arXiv 2022

  28. [28]

    H˚ astad, Some optimal inapproximability results, Jour- nal of the ACM 48, 798 (2001)

    J. H˚ astad, Some optimal inapproximability results, Jour- nal of the ACM 48, 798 (2001)

    work page 2001

  29. [29]

    M. X. Goemans and D. P. Williamson, Improved approx- imation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM 42, 1115 (1995)

    work page 1995

  30. [30]

    Quantum computing with Qiskit

    A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, B. R. Johnson, and J. M. Gambetta, Quantum computing with Qiskit (2024), arXiv:2405.08810 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  31. [31]

    E. B. Wilson, Probable Inference, the Law of Succession, and Statistical Inference, Journal of the American Sta- tistical Association 22, 209 (1927)

    work page 1927

  32. [32]

    Seabold and J

    S. Seabold and J. Perktold, statsmodels: Econometric and statistical modeling with python, in 9th Python in Science Conference (2010)

    work page 2010

  33. [33]

    Additional arguments, which would be required, e.g., for gradient- based optimization algorithms would not affect any of the arguments presented in the following

    Note that for simplicity of notation, we assume the opti- mization algorithm only takes the parameter values and the current cost function value as in input. Additional arguments, which would be required, e.g., for gradient- based optimization algorithms would not affect any of the arguments presented in the following

    work page

  34. [34]

    P. K. Barkoutsos, G. Nannicini, A. Robert, I. Tav- ernelli, and S. Woerner, Improving Variational Quan- tum Optimization using CVaR, Quantum 4, 256 (2020), arXiv:1907.04769

    work page arXiv 2020

  35. [35]

    M. J. D. Powell, Direct search algorithms for optimiza- tion calculations, Acta Numerica 7, 287 (1998)

    work page 1998

  36. [36]

    Virtanen, R

    P. Virtanen, R. Gommers, T. E. Oliphant, M. Haber- land, T. Reddy, D. Cournapeau, E. Burovski, P. Pe- terson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, ˙I. Po- lat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henr...

    work page 2020

  37. [37]

    X. Liu, A. Angone, R. Shaydulin, I. Safro, Y. Alexeev, and L. Cincio, Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Com- puters, IEEE Transactions on Quantum Engineering 3, 1 (2022), arXiv:2102.05566

    work page arXiv 2022

  38. [38]

    Scriva, N

    G. Scriva, N. Astrakhantsev, S. Pilati, and G. Maz- zola, Challenges of variational quantum optimiza- tion with measurement shot noise , Tech. Rep. (2023) arXiv:2308.00044

    work page arXiv 2023

  39. [39]

    Marin-Sanchez and D

    G. Marin-Sanchez and D. Amaro, Performance analysis of a filtering variational quantum algorithm , Tech. Rep. (2024) arXiv:2404.08933

    work page arXiv 2024

  40. [40]

    Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual (2023)

    work page 2023

  41. [41]

    Dupont, B

    M. Dupont, B. Evert, M. J. Hodson, B. Sundar, S. Jef- frey, Y. Yamaguchi, D. Feng, F. B. Maciejewski, S. Had- field, M. S. Alam, Z. Wang, S. Grabbe, P. A. Lott, E. G. Rieffel, D. Venturelli, and M. J. Reagor, Quantum- Enhanced Greedy Combinatorial Optimization Solver, Science Advances 9, eadi0487 (2023), arXiv:2303.05509

    work page arXiv 2023

  42. [42]

    Sciorilli, L

    M. Sciorilli, L. Borges, T. L. Patti, D. Garc´ ıa-Mart´ ın, G. Camilo, A. Anandkumar, and L. Aolita, Towards large-scale quantum optimization solvers with few qubits , Tech. Rep. (2024) arXiv:2401.09421

    work page arXiv 2024

  43. [43]

    C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gom- mers, P. Virtanen, D. Cournapeau, E. Wieser, J. Tay- lor, S. Berg, N. J. Smith, R. Kern, M. Picus, S. Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. del R´ ıo, M. Wiebe, P. Peterson, P. G´ erard-Marchant, K. Shep- pard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T. E. Oliphant, Array ...

    work page 2020

  44. [44]

    Y. Chai, K. Jansen, S. K¨ uhn, T. Schw¨ agerl, and T. Stol- lenwerk, Structure-inspired ansatz and warm start of variational quantum algorithms for quadratic uncon- strained binary optimization problems, arXiv:2407.02569 , (2024)

    work page arXiv 2024