Are quantum computers suitable for solving combinatorial optimization problems efficiently?

There is much talk about the capabilities of quantum computing, in particular that quantum computers will revolutionize the solution of NP-hard combinatorial optimization problems, such as those encountered in logistics or portfolio optimization. In fact, there is no evidence, let alone proof, that this can be achieved with future quantum gate computers (using hybrid QAOA or VQE algorithms) or existing quantum annealers, even though D-Wave repeatedly claims that their machines already generate business value.

The peer-reviewed paper "Isermann, S. Improved Posiform Planting Algorithm for Random Generation of Binary Optimization Problems. SN COMPUT. SCI. 6, 475 (2025). https://doi.org/10.1007/s42979-025-03964-9" now presents an algorithm that can generate random optimization problems with a known absolute minimum, particularly tailored to the weakly connected structures of a quantum annealer. If you are interested in graph theory and this particular algorithm, you can read a full-text version of the paper as part of the Springer Nature SharedIt initiative by using this link.

Anyone who still believes in the magical capabilities of a quantum annealer can use this algorithm to benchmark classical approaches (e.g., Restricted Boltzmann Machines) against a quantum annealer. If a quantum advantage were to be observed here, it would be very surprising and certainly worth another publication.