% IMPORTANT: The following is UTF-8 encoded.  This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.

@ARTICLE{Schwgerl:614736,
      author       = {Schwägerl, Tim and Chai, Yahui and Hartung, Tobias and
                      Jansen, Karl and Kühn, Stefan},
      title        = {{B}enchmarking {V}ariational {Q}uantum {A}lgorithms for
                      {C}ombinatorial {O}ptimization in {P}ractice},
      reportid     = {PUBDB-2024-05956, arXiv:2408.03073},
      year         = {2024},
      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.},
      cin          = {HUB / $Z_ET$},
      cid          = {I:(DE-H253)HUB-20140108 / $I:(DE-H253)Z_ET-20210408$},
      pnm          = {611 - Fundamental Particles and Forces (POF4-611) / QUEST -
                      QUantum computing for Excellence in Science and Technology
                      (101087126) / HiggsSelfCoupling - Uncovering the Origins of
                      Mass: Discovery of the di-Higgs Process and Constraints on
                      the Higgs Self-Coupling (787331)},
      pid          = {G:(DE-HGF)POF4-611 / G:(EU-Grant)101087126 /
                      G:(EU-Grant)787331},
      experiment   = {EXP:(DE-MLZ)NOSPEC-20140101},
      typ          = {PUB:(DE-HGF)25},
      eprint       = {2408.03073},
      howpublished = {arXiv:2408.03073},
      archivePrefix = {arXiv},
      SLACcitation = {$\%\%CITATION$ = $arXiv:2408.03073;\%\%$},
      doi          = {10.3204/PUBDB-2024-05956},
      url          = {https://bib-pubdb1.desy.de/record/614736},
}