CoChat
Sign Up
PreprintCited by 5Quantum Computing Algorithms and ArchitectureMetaheuristic Optimization Algorithms ResearchAdvanced Optimization Algorithms Research

The DOI matches its DataCite record.

Quantum Optimization Benchmarking Library - The Intractable Decathlon

Open access
Koch, Thorsten, Neira, David E. Bernal, Chen, Ying, Cortiana, Giorgio, Egger, Daniel J., Heese, Raoul, Hegade, Narendra N., Cadavid, Alejandro Gomez, Huang, Rhea, Itoko, Toshinari, Kleinert, Thomas, Xavier, Pedro Maciel, Mohseni, Naeimeh, Montanez-Barrera, Jhon A., Nakano, Koji, Nannicini, Giacomo, O'Meara, Corey, Pauckert, Justin, Proissl, Manuel, Ramesh, Anurag, Schicker, Maximilian, Shimada, Noriaki, Takeori, Mitsuharu, Valls, Victor, Van Bulck, David, Woerner, Stefan, Zoufal, Christa·2025·arXiv
DOI 10.48550/arxiv.2504.03832arXiv 2504.03832PMC PMC13293884

Preprint — published as 10.1038/s43588-026-00991-1

Open this paper in CoChat — free accountOpen PDF

Abstract

Through recent progress in hardware development, quantum computers have advanced to the point where benchmarking of (heuristic) quantum algorithms at scale is within reach. Particularly in combinatorial optimization - where most algorithms are heuristics - it is key to empirically analyze their performance on hardware and track progress towards quantum advantage. To this extent, we present ten optimization problem classes that are difficult for existing classical algorithms and can (mostly) be linked to practically relevant applications, with the goal to enable systematic, fair, and comparable benchmarks for quantum optimization methods. Further, we introduce the Quantum Optimization Benchmarking Library (QOBLIB) where the problem instances and solution track records can be found. The individual properties of the problem classes vary in terms of objective and variable type, coefficient ranges, and density. Crucially, they all become challenging for established classical methods already at system sizes ranging from less than 100 to, at most, an order of 100,000 decision variables, allowing to approach them with today's quantum computers. We reference the results from state-of-the-art solvers for instances from all problem classes and demonstrate exemplary baseline results obtained with quantum solvers for selected problems. The baseline results illustrate a standardized form to present benchmarking solutions, which has been designed to ensure comparability of the used methods, reproducibility of the respective results, and trackability of algorithmic and hardware improvements over time. We encourage the optimization community to explore the performance of available classical or quantum algorithms and hardware platforms with the benchmarking problem instances presented in this work toward demonstrating quantum advantage in optimization.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2504.03832

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 142

  1. [2]Goemans, M. X. & Williamson, D. P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115–1145 (1995). · DOI · Paper page
  2. [3]Khot, S., Kindler, G., Mossel, E. & O’Donnell, R. Optimal inapproximability results for MAX CUT and other 2 variable CSPs?. SIAM J. Comput. 37, 319–357 (2007). · DOI
  3. [4]Kim, Y. et al. Evidence for the utility of quantum computing before fault tolerance. Nature 618, 500–505 (2023). 37316724 PMC10266970 · DOI · Paper page
  4. [7]Müller, M., Whitney, B., Henschel, R. and Kumaran, K. In SPEC Benchmarks 1886–1893 (Springer, 2011).
  5. [9]Koch, T. et al. Progress in mathematical programming solvers from 2001 to 2020. EURO J. Comput. Optim. 10, 100031 (2022). · DOI
  6. [10]Dunning, I., Gupta, S. & Silberholz, J. What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO. INFORMS J. Comput. 30, 608–624 (2018). · DOI · Paper page
  7. [12]Froleyks, N., Heule, M., Iser, M., Järvisalo, M. & Suda, M. SAT competition 2020. Artif. Intell. 301, 103572 (2021). · DOI
  8. [14]Gleixner, A. et al. MIPLIB 2017: data-driven compilation of the 6th Mixed-Integer Programming Library. Math. Program. Comput. 13, 443–490 (2021). · DOI
  9. [16]Proctor, T., Young, K., Baczewski, A. D. & Blume-Kohout, R. Benchmarking quantum computers. Nat. Rev. Phys. 7, 105–118 (2025). · DOI
  10. [17]Acuaviva, A., Aguirre, D., Peña, R. & Sanz, M. Benchmarking quantum computers: towards a standard performance evaluation approach. Quantum Sci. Technol. 11, 025004 (2026). · DOI
  11. [18]Lorenz, J. M. et al. Systematic benchmarking of quantum computers: status and recommendations. Preprint at https://arxiv.org/abs/2503.04905 (2025). · arXiv
  12. [19]Magesan, E. et al. Efficient measurement of quantum gate error by interleaved randomized benchmarking. Phys. Rev. Lett. 109, 080505 (2012). 23002731 · DOI
  13. [20]McKay, D. C. et al. Benchmarking quantum processor performance at scale. Preprint at https://arxiv.org/abs/2311.05933 (2023). · arXiv
  14. [21]Nation, P. D. et al. Benchmarking the performance of quantum computing software. Nat. Comput. Sci. 5, 427–435 (2025). 40251256 PMC12116379 · DOI
  15. [22]Wack, A. et al. Quality, speed, and scale: three key attributes to measure the performance of near-term quantum computers. Preprint at https://arxiv.org/abs/2110.14108 (2021). · arXiv
  16. [23]Granet, E. & Dreyer, H. AppQSim: application-oriented benchmarks for Hamiltonian simulation on a quantum computer. Phys. Rev. Research 7, 043146 (2025). · DOI
  17. [24]Martiel, S., Ayral, T. & Allouche, C. Benchmarking quantum coprocessors in an application-centric, hardware-agnostic, and scalable way. IEEE Trans. Quantum Eng. 2, 1–11 (2021). · DOI
  18. [25]Lubinski, T. et al. Optimization applications as quantum performance benchmarks. ACM Trans. Quantum Comput. 5, 3 (2024). · DOI
  19. [26]Tomesh, T. et al. SupermarQ: a scalable quantum benchmark suite. In 2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA) 587–603 (IEEE, 2022).
  20. [27]Santra, G. C., Jendrzejewski, F., Hauke, P. & Egger, D. J. Squeezing and quantum approximate optimization. Phys. Rev. A 109, 012413 (2024). · DOI
  21. [28]Finžgar, J. R., Ross, P., Hölscher, L., Klepsch, J. & Luckow, A. QUARK: a framework for quantum computing application benchmarking. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) 226–237 (IEEE, 2022).
  22. [29]McGeoch, C. How not to fool the masses when giving performance results for quantum computers. Preprint at https://arxiv.org/abs/2411.08860 (2024). · arXiv
  23. [30]Bernal Neira, D. E. et al. Benchmarking the operation of quantum heuristics and Ising machines: scoring parameter setting strategies on optimization applications. Quantum Mach. Intell. 7, 86 (2025). 40917685 PMC12413341 · DOI
  24. [31]Lall, D. et al. A review and collection of metrics and benchmarks for quantum computers: definitions, methodologies and software. Preprint at https://arxiv.org/abs/2502.06717 (2025). · arXiv
  25. [32]Wu, D. et al. Variational benchmarks for quantum many-body problems. Science 386, 296–301 (2024). 39418373 · DOI · Paper page
  26. [33]Karp, R. M. Reducibility among combinatorial problems. In Complexity of Computer Computations: Proc. Symposium on the Complexity of Computer Computations (eds Miller, R. E. et al.) 85–103 (Springer, 1972).
  27. [34]Agarwal, P. K., Van Kreveld, M. & Suri, S. Label placement by maximum independent set in rectangles. Comput. Geom. 11, 209–218 (1998). · DOI
  28. [35]Hossain, A. et al. Automated design of thousands of nonrepetitive parts for engineering stable genetic systems. Nat. Biotechnol. 38, 1466–1475 (2020). 32661437 · DOI
  29. [36]Wurtz, J. et al. Industry applications of neutral-atom quantum computing solving independent set problems. Preprint at https://arxiv.org/abs/2205.08500 (2022). · arXiv
  30. [37]Xiao, M. & Nagamochi, H. Exact algorithms for maximum independent set. Inf. Comput. 255, 126–146 (2017). · DOI
  31. [38]Bazgan, C., Escoffier, B. & Paschos, V. T. Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness. Theor. Comput. Sci. 339, 272–292 (2005). · DOI
  32. [39]Clark, B. N., Colbourn, C. J. & Johnson, D. S. Unit disk graphs. Discret. Math. 86, 165–177 (1990). · DOI
  33. [40]Ebadi, S. et al. Quantum optimization of maximum independent set using Rydberg atom arrays. Science 376, 1209–1215 (2022). 35511943 · DOI · Paper page
  34. [41]Marathe, M. V., Breu, H., Hunt, H. B. III, Ravi, S. S. & Rosenkrantz, D. J. Simple heuristics for unit disk graphs. Networks 25, 59–68 (1995). · DOI
  35. [42]Das, G. K., da Fonseca, G. D. & Jallu, R. K. Efficient independent set approximation in unit disk graphs. Discret. Appl. Math. 280, 63–70 (2020). · DOI
  36. [44]Rossi, R., & Ahmed, N. The network data repository with interactive graph analytics and visualization. In Proc. AAAI Conference on Artificial Intelligence, Vol. 29 (2015); 10.1609/aaai.v29i1.9277 · DOI
  37. [46]Farhi, E., Goldstone, J. & Gutmann, S. A quantum approximate optimization algorithm. Preprint at https://arxiv.org/abs/1411.4028 (2014). · arXiv
  38. [48]Egger, D. J., Mareček, J. & Woerner, S. Warm-starting quantum optimization. Quantum 5, 479 (2021). · DOI · Paper page
  39. [49]Alessandroni, E., Ramos-Calderer, S., Roth, I., Traversi, E. & Aolita, L. Alleviating the quantum Big-M problem. Preprint at https://arxiv.org/abs/2307.10379 (2024). · arXiv
  40. [50]Virtanen, P. et al. SciPy 1.0: fundamental algorithms for scientific computing in Python. Nat. Methods 17, 261–272 (2020). 32015543 PMC7056644 · DOI · Paper page
  41. [52]Weidenfeller, J. et al. Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware. Quantum 6, 870 (2022). · DOI
  42. [53]Bennett, C. H., Bernstein, E., Brassard, G. & Vazirani, U. Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 1510–1523 (1997). · DOI · Paper page
  43. [54]de Wolf, R. Quantum computing: lecture notes. Preprint at https://arxiv.org/abs/1907.09415 (2023). · arXiv
  44. [55]Durr, C. & Hoyer, P. A quantum algorithm for finding the minimum. Preprint at https://arxiv.org/abs/quant-ph/9607014 (1999). · arXiv
  45. [56]Gilliam, A., Woerner, S. & Gonciulea, C. Grover adaptive search for constrained polynomial binary optimization. Quantum 5, 428 (2021). · DOI · Paper page
  46. [57]Jordan, S. P. et al. Optimization by decoded quantum interferometry. Nature 646, 831–836 (2025). 41125774 PMC12545177 · DOI
  47. [58]Schrijver, A. Combinatorial Optimization (Springer, 2003).
  48. [60]Lucas, A. Ising formulations of many NP problems. Front. Phys. 2, 5 (2014). · DOI · Paper page
  49. [62]Pelofske, E., Bärtschi, A. & Eidenbenz, S. Short-depth QAOA circuits and quantum annealing on higher-order Ising models. npj Quantum Inf. 10, 30 (2024). · DOI
  50. [63]Anthony, M., Boros, E., Crama, Y. & Gruber, A. Quadratic reformulations of nonlinear binary optimization problems. Math. Program. 162, 115–144 (2017). · DOI
  51. [64]Glover, F., Kochenberger, G. & Du, Y. A tutorial on formulating and using QUBO models. 4OR 17, 335–371 (2019). · DOI · Paper page
  52. [65]Xavier, P. M. et al. Disjunctive programming meets QUBO. In Computer Aided Chemical Engineering Vol. 53 (eds Manenti, F. & Reklaitis, G. V.) 3433–3438 (Elsevier, 2024).
  53. [66]Berthold, T. Measuring the impact of primal heuristics. Oper. Res. Lett. 41, 611–614 (2013). · DOI
  54. [67]Kool, W., van Hoof, H. & Welling, M. Attention, learn to solve routing problems! In International Conference on Learning Representations (ICLR 2019) (2019).
  55. [68]Berto, F. et al. RL4CO: an extensive reinforcement learning for combinatorial optimization benchmark. In KDD 2025 — Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining 5278–5289 (ACM, 2025).
  56. [70]Javadi-Abhari, A. et al. Quantum computing with Qiskit. Preprint at https://arxiv.org/abs/2405.08810 (2024). · arXiv
  57. [71]Sciorilli, M. et al. Towards large-scale quantum optimization solvers with few qubits. Nat. Commun. 16, 476 (2025). 39774687 PMC11707289 · DOI · Paper page
  58. [72]Gérard Cornuéjols, M. D. Class of hard small 0–1 programs. INFORMS J. Comput. 11, 205–210 (1999). · DOI
  59. [74]Schroeppel, R. & Shamir, A. A t = O (2 n/2), s = O (2 n/4) algorithm for certain NP-complete problems. SIAM J. Comput. 10, 456–464 (1981). · DOI
  60. [75]Wassermann, A. Attacking the market split problem with lattice point enumeration. J. Comb. Optim. 6, 5–16 (2002). · DOI
  61. [76]Aardal, K., Bixby, R. E., Hurkens, C. A. J., Lenstra, A. K. & Smeltink, J. W. Market split and basis reduction: towards a solution of the Cornuéjols–Dawande instances. INFORMS J. Comput. 12, 192–202 (2000). · DOI
  62. [77]Boehmer, A. Binary pulse compression codes. IEEE Trans. Inf. Theory 13, 156–167 (1967). · DOI
  63. [78]Mertens, S. & Bessenrodt, C. On the ground states of the Bernasconi model. J. Phys. A 31, 3731–3750 (1998). · DOI
  64. [79]Elloumi, S., Lambert, A. & Lazare, A. Solving unconstrained 0–1 polynomial programs through quadratic convex reformulation. J. Glob. Optim. 80, 231–248 (2021). · DOI
  65. [81]Packebusch, T. & Mertens, S. Low autocorrelation binary sequences. J. Phys. A 49, 165001 (2016). · DOI · Paper page
  66. [82]Gallardo, J. E., Cotta, C. & Fernández, A. J. Finding low autocorrelation binary sequences with memetic algorithms. Appl. Soft Comput. 9, 1252–1262 (2009). · DOI · Paper page
  67. [83]Shaydulin, R. et al. Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem. Sci. Adv. 10, eadm6761 (2024). 38809986 PMC11135426 · DOI · Paper page
  68. [84]Zhang, Z., Shen, J., Kumar, N. & Pistoia, M. New improvements in solving large LABS instances using massively parallelizable memetic tabu search. Preprint at https://arxiv.org/abs/2504.00987 (2025). · arXiv
  69. [85]Dufossé, F. & Uçar, B. Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices. Linear Algebra Its Appl. 497, 108–115 (2016). · DOI
  70. [87]Brualdi, R. A. Notes on the Birkhoff algorithm for doubly stochastic matrices. Can. Math. Bull. 25, 191–199 (1982). · DOI
  71. [88]Marcus, M. & Ree, R. Diagonals of doubly stochastic matrices. Q. J. Math. 10, 296–302 (1959). · DOI
  72. [89]Kulkarni, J., Lee, E. & Singh, M. in Integer Programming and Combinatorial Optimization (eds Eisenbrand, F. & Koenemann, J.) 343–354 (Springer, 2017).
  73. [90]Chang, C. S., Chen, W. J. & Huang, H. Y. Birkhoff–von Neumann input buffered crossbar switches. In Proc. IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies Vol. 3 1614–1623 (IEEE, 2000).
  74. [91]Ye, T., Zhang, J., Lee, T. T. & Hu, W. Deflection-compensated Birkhoff–von-Neumann switches. IEEE/ACM Trans. Netw. 25, 879–895 (2017). · DOI
  75. [92]Liu, H. et al. Scheduling techniques for hybrid circuit/packet networks. In Proc. 11th ACM Conference on Emerging Networking Experiments and Technologies 41 (Association for Computing Machinery, 2015).
  76. [93]O’Meara, C., Fernández-Campoamor, M., Cortiana, G. & Bernabé-Moreno, J. Quantum software architecture blueprints for the Cloud: overview and application to peer-2-peer energy trading. In 2023 IEEE Conference on Technologies for Sustainability (SusTech) 191–198 (IEEE, 2023).
  77. [94]Hendrych, D., Troppens, H., Besançon, M. & Pokutta, S. Convex mixed-integer optimization with Frank–Wolfe methods. Math. Prog. Comp. 17, 731–757 (2025). · DOI
  78. [95]Combettes, C. W. & Pokutta, S. Revisiting the approximate Carathéodory problem via the Frank–Wolfe algorithm. Math. Program. 197, 191–214 (2023). · DOI
  79. [96]Valls, V., Iosifidis, G. & Tassiulas, L. Birkhoff’s decomposition revisited: sparse scheduling for high-speed circuit switches. IEEE/ACM Trans. Netw. 29, 2399–2412 (2021). · DOI
  80. [97]Mariella, N. et al. Quantum theory and application of contextual optimal transport. In Proc. 41st International Conference on Machine Learning Vol. 235, 34822–34845 (2024).
  81. [98]Arora, S. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In Proc. 37th Conference on Foundations of Computer Science 2–11 (IEEE, 1996).
  82. [99]Hakimi, S. L. Steiner’s problem in graphs and its implications. Networks 1, 113–133 (1971). · DOI
  83. [100]Grötschel, M., Martin, A. & Weismantel, R. The Steiner tree packing problem in VLSI design. Math. Program. 78, 265–281 (1997). · DOI
  84. [101]Grötschel, M., Martin, A. & Weismantel, R. Packing Steiner trees: polyhedral investigations. Math. Program. 72, 101–123 (1996). · DOI
  85. [102]Grötschel, M., Martin, A. & Weismantel, R. Packing Steiner trees: separation algorithms. SIAM J. Discret. Math. 9, 233–257 (1996). · DOI
  86. [103]Jain, K., Mahdian, M. & Salavatipour, M. R. Packing Steiner trees. In SODA '03: Proc. Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms Vol. 3 266–274 (Society for Industrial and Applied Mathematics, 2003).
  87. [105]Kaski, P. & Östergård, P. R. J. There are 1,132,835,421,602,062,347 nonisomorphic one-factorizations of K 14. J. Comb. Des. 17, 147–159 (2009). · DOI
  88. [106]van Doornmalen, J., Hojny, C., Lambers, R. & Spieksma, F. C. R. Integer programming models for round robin tournaments. Eur. J. Oper. Res. 310, 24–33 (2023). · DOI
  89. [107]Nemhauser, G. L. & Trick, M. A. Scheduling a major college basketball conference. Oper. Res. 46, 1–8 (1998). · DOI
  90. [108]Van Bulck, D. & Goossens, D. A traditional Benders’ approach to sports timetabling. Eur. J. Oper. Res. 307, 813–826 (2023). · DOI
  91. [109]Van Bulck, D. & Goossens, D. The international timetabling competition on sports timetabling (ITC2021). Eur. J. Oper. Res. 308, 1249–1267 (2023). · DOI
  92. [112]Kolm, P. N., Tütüncü, R. & Fabozzi, F. J. 60 years of portfolio optimization: practical challenges and current trends. Eur. J. Oper. Res. 234, 356–371 (2014). · DOI
  93. [113]Haff, L. R. Empirical Bayes estimation of the multivariate normal covariance matrix. Ann. Stat. 8, 586–597 (1980). · DOI
  94. [114]Ben-Tal, A. & Nemirovski, A. Robust solutions of uncertain linear programs. Oper. Res. Lett. 25, 1–13 (1999). · DOI
  95. [115]Black, F. & Litterman, R. Global portfolio optimization. Financ. Anal. J. 48, 28–43 (1992). · DOI
  96. [116]Michaud, R. O. & Ma, T. Efficient asset management: a practical guide to stock portfolio optimization and asset allocation. Rev. Financ. Stud. 14, 901–904 (2015). · DOI
  97. [117]Merton, R. C. Lifetime portfolio selection under uncertainty: the continuous-time case. Rev. Econ. Stat. 51, 247–257 (1969). · DOI
  98. [118]DeMiguel, V., Garlappi, L. & Uppal, R. Optimal versus naive diversification: how inefficient is the 1/ n portfolio strategy?. Rev. Financ. Stud. 22, 1915–1953 (2007). · DOI · Paper page
  99. [119]López de Prado, M. Building diversified portfolios that outperform out of sample. J. Portf. Manag. 42, 59–69 (2016). · DOI
  100. [120]Gava, J. & Turc, J. The properties of alpha risk parity portfolios. Entropy 24, 1631 (2022). 36359721 PMC9689940 · DOI
  101. [121]Almgren, R. & Chriss, N. Optimal execution of portfolio transactions. J. Risk 3, 5–39 (2000). · DOI
  102. [122]Palczewski, J., Poulsen, R., Schenk-Hoppé, K. R. & Wang, H. Dynamic portfolio optimization with transaction costs and state-dependent drift. Eur. J. Oper. Res. 243, 921–931 (2015). · DOI
  103. [123]Kolm, P. N. and Ritter, G. Modern perspectives on reinforcement learning in finance. SSRN Electron. J. (2019).
  104. [124]Brown, D. B. & Smith, J. E. Dynamic portfolio optimization with transaction costs: heuristics and dual bounds. Manag. Sci. 57, 1752–1770 (2011). · DOI
  105. [125]Constantinides, G. M. Multiperiod consumption and investment behavior with convex transactions costs. Manag. Sci. 25, 1127–1137 (1979). · DOI
  106. [126]Kerenidis, I., Prakash, A. & Szilágyi, D. Quantum algorithms for portfolio optimization. In Proc. 1st ACM Conference on Advances in Financial Technologies 147–155 (Association for Computing Machinery, 2019).
  107. [127]Rosenberg, G. et al. Solving the optimal trading trajectory problem using a quantum annealer. IEEE J. Sel. Top. Signal Process. 10, 1053–1060 (2016). · DOI
  108. [128]Lim, D. & Rebentrost, P. A quantum online portfolio optimization algorithm. Quantum Inf. Process. 23, 63 (2024). · DOI
  109. [129]Brandhofer, S. et al. Benchmarking the performance of portfolio optimization with QAOA. Quantum Inf. Process. 22, 25 (2022). · DOI · Paper page
  110. [130]Slate, N., Matwiejew, E., Marsh, S. & Wang, J. B. Quantum walk-based portfolio optimisation. Quantum 5, 513 (2021). · DOI
  111. [131]Mugel, S. et al. Dynamic portfolio optimization with real datasets using quantum processors and quantum-inspired tensor networks. Phys. Rev. Res. 4, 013006 (2022). · DOI
  112. [132]Bienstock, D. Computational study of a family of mixed-integer quadratic programming problems. Math. Program. 74, 121–140 (1996). · DOI
  113. [133]Gavish, B. Topological design of telecommunication networks—local access design methods. Ann. Oper. Res. 33, 17–71 (1991). · DOI
  114. [134]Magnanti, T. L. & Wong, R. T. Network design and transportation planning: models and algorithms. Transp. Sci. 18, 1–55 (1984). · DOI
  115. [135]Saberi, R. et al. Power distribution network expansion planning to improve resilience. IET Gener. Transm. Distrib. 17, 4701–4716 (2023). · DOI
  116. [136]Bienstock, D. & Günlük, O. Computational experience with a difficult mixedinteger multicommodity flow problem. Math. Program. 68, 213–237 (1995). · DOI
  117. [137]Bienstock, D., Chopra, S., Günlük, O. & Tsai, C.-Y. Minimum cost capacity installation for multicommodity network flows. Math. Program. 81, 177–199 (1998). · DOI
  118. [138]Gendron, B., Crainic, T. G. & Frangioni, A. in Telecommunications Network Planning (eds Sansò, B. & Soriano, P.) 1–19 (Springer, 1999).
  119. [139]Armacost, A. P., Barnhart, C. & Ware, K. A. Composite variable formulations for express shipment service network design. Transp. Sci. 36, 1–20 (2002). · DOI
  120. [140]Magnanti, T. L., Mireault, P. & Wong, R. T. Tailoring Benders Decomposition for Uncapacitated Network Design (Springer, 1986).
  121. [141]Barnhart, C. & Schneur, R. R. Air network design for express shipment service. Oper. Res. 44, 852–863 (1996). · DOI
  122. [142]Dantzig, G. B. & Ramser, J. H. The truck dispatching problem. Manag. Sci. 6, 80–91 (1959). · DOI
  123. [144]Xie, N. et al. A feasibility-preserved quantum approximate solver for the capacitated vehicle routing problem. Quantum Inf. Process. 23, 291 (2024). · DOI
  124. [145]Mohanty, N., Behera, B. K. & Ferrie, C. Analysis of the vehicle routing problem solved via hybrid quantum algorithms in the presence of noisy channels. IEEE Trans. Quantum Eng.4 (2023).
  125. [146]Leonidas, I. D. et al. Qubit efficient quantum algorithms for the vehicle routing problem on noisy intermediate-scale quantum processors. Adv. Quantum Technol. 7, 2300309 (2024). · DOI
  126. [147]Fitzek, D., Ghandriz, T., Laine, L., Granath, M. & Kockum, A. F. Applying quantum approximate optimization to the heterogeneous vehicle routing problem. Sci. Rep. 14, 25415 (2021). PMC11512041 39455701 · DOI
  127. [148]Miller, C. E., Tucker, A. W. & Zemlin, R. A. Integer programming formulation of traveling salesman problems. J. ACM 7, 326–329 (1960). · DOI
  128. [149]Sidorov, K. & Morozov, A. A review of approaches to modeling applied vehicle routing problems. Preprint at https://arxiv.org/abs/2105.10950 (2021). · arXiv
  129. [150]Clarke, G. & Wright, J. W. Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12, 568–581 (1964). · DOI
  130. [151]Muriyatmoko, D., Djunaidy, A. & Muklason, A. Heuristics and metaheuristics for solving capacitated vehicle routing problem: an algorithm comparison. Procedia Comput. Sci. 234, 494–501 (2024). · DOI
  131. [152]El Jaouhari, M., Bencheikh, G. & Bencheikh, G. Exploring the capacitated vehicle routing problem using the power of machine learning: a literature review. In Proc. 7th International Conference on Logistics Operations Management, GOL’24 (eds Benadada, Y. et al.) 68–80 (Springer Nature, 2024).
  132. [153]Harikrishnakumar, R., Nannapaneni, S., Nguyen, N. H., Steck, J. E. & Behrman, E. C. A quantum annealing approach for dynamic multi-depot capacitated vehicle routing problem. Preprint at https://arxiv.org/abs/2005.12478 (2020). · arXiv
  133. [154]Applegate, D., Bixby, R., Chvátal, V. & Cook, W. Implementing the Dantzig–Fulkerson–Johnson algorithm for large traveling salesman problems. Math. Program. 97, 91–153 (2003). · DOI
  134. [155]Lenstra, J. K. & Kan, A. H. G. R. Complexity of vehicle routing and scheduling problems. Networks 11, 221–227 (1981). · DOI
  135. [156]Munari, P., Dollevoet, T. & Spliet, R. A generalized formulation for vehicle routing problems. Preprint at https://arxiv.org/abs/1606.01935 (2017). · arXiv
  136. [157]Hoffman, A. J. & Singleton, R. R. On Moore graphs with diameters 2 and 3. IBM J. Res. Dev. 4, 497–504 (1960). · DOI
  137. [158]Cerf, V. G., Cowan, D. D., Mullin, R. C. & Stanton, R. G. A lower bound on the average shortest path length in regular graphs. Networks 4, 335–342 (1974). · DOI
  138. [159]Shin, J. Y., Wong, B. & Sirer, E. G. Small-world datacenters. In Proc. 2nd ACM Symposium on Cloud Computing 2 (Association for Computing Machinery, 2011).
  139. [160]Besta M. & Hoefler, T. Slim Fly: a cost effective low-diameter network topology. In SC’14: Proc. International Conference for High Performance Computing, Networking, Storage and Analysis 348–359 (IEEE, 2014).
  140. [161]Singla, A., Hong, C. Y., Popa, L. & Godfrey, P. B. Jellyfish: networking data centers randomly. In 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12) 225–238 (USENIX Association, 2012).
  141. [163]Waniek, R. Graph Golf: Betrachtung des Order-Degree-Problems. Master’s thesis, Technische Univ. Berlin (2021).
  142. [166]Koch, T. Rapid Mathematical Programming. PhD thesis, Technische Univ. Berlin, ZIB-Report 04-58 (2004).

Cited by

Sorted by citations

Metadata

Authors
Koch, T., Neira, D. E. B., Chen, Y., Cortiana, G., Egger, D. J., Heese, R., Hegade, N. N., Cadavid, A. G., Huang, R., Itoko, T., Kleinert, T., Xavier, P. M., Mohseni, N., Montanez-Barrera, J. A., Nakano, K., Nannicini, G., O'Meara, C., Pauckert, J., Proissl, M., Ramesh, A., Schicker, M., Shimada, N., Takeori, M., Valls, V., Van Bulck, D., Woerner, S., & Zoufal, C.
Affiliations
  • Zuse Institute Berlin (DE)
  • Purdue University West Lafayette (US)
  • National University of Singapore (SG)
  • E.ON (Germany) (DE)
  • IBM Research - Zurich (CH)
  • NTT (Japan) (JP)
  • University of the Basque Country (ES)
  • University of Southern California (US)
  • IBM Research - Tokyo (JP)
  • Universidade Federal do Rio de Janeiro (BR)
  • Hiroshima University (JP)
Corresponding author
  • Koch, Thorsten
  • Woerner, Stefan
  • Zoufal, Christa
ORCID
Venue
arXiv
Publisher
arXiv
Published
2025
Volume
6
Issue
6
Pages
653-671
ISSN
2662-8457 (ISSN-L)
DOI
10.48550/arxiv.2504.03832
arXiv
2504.03832
PMC
PMC13293884
OpenAlex
W4414430030
Cited by
5
References
0
Citations by year
2026: 5
FWCI
17.09
Type
journal article
Language
en
Open access
Licence
Locations
  • Nature Computational Science (publishedVersion, cc-by-nc-nd)
  • PubMed (publishedVersion)
  • PubMed Central (publishedVersion, cc-by-nc-nd)
  • arXiv (Cornell University) (submittedVersion, cc-by)
  • Ghent University Academic Bibliography (Ghent University) (submittedVersion, cc-by-nc-nd)
  • arXiv (Cornell University) (cc-by)
Funders
  • National Research Foundation
  • National Research Foundation Singapore (A-8000014-00-00)
  • Ministry of Education - Singapore (A-8000339-01-00)
  • Bundesministerium für Bildung und Forschung (05M20ZBM, 05M2025, 05M14ZAM)
  • Fonds Wetenschappelijk Onderzoek (23AXE35N)
  • Vlaamse regering
  • Office of Naval Research (N000142312585)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
  • Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
Keywords
quantum optimization, benchmarking, combinatorial optimization, quantum advantage, problem classes, benchmark instances

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review