No. 145 
No. 144 
No. 143 
No. 142 
No. 141 
No. 140 
No. 139 by Pascal Halffmann (Fraunhofer Institute for Industrial Mathematics ITWM)
Hardness alone does not identify promising quantum applications. Classical optimization has spent decades exploiting problem structure; thus, quantum methods must compete with far more than brute force. Where, then, might quantum optimization genuinely contribute, and what kinds of problems offer a plausible path to real-world utility or even advantage?
Quantum optimization is booming
Quantum optimization has become a highly active area of quantum computing. A search of arXiv’s Quantum Physics category identified 182 preprints related to quantum optimization that were published this year until September 1 [L1]. The appeal is clear: optimization problems are ubiquitous, economically important, and often computationally hard. To date, no quantum approach has demonstrated a practical advantage over classical methods in solution time or quality. Some critics therefore question whether such an advantage is attainable at all.
What theory actually promises
Aaronson’s “law of conservation of weirdness” expresses the intuition that exponential quantum speedups require unusual problem structure. The related, unproven Aaronson–Ambainis conjecture concerns the black-box/query model stating that a quantum algorithm’s acceptance probability (“yes”- vs. “no”-answer) can be approximated classically, to fixed additive accuracy, on most inputs with only polynomial overhead. If true, it rules out generic exponential query speedups for decision problems on typical unstructured inputs but does not prohibit quantum advantage: It does not establish efficient classical simulation of arbitrary quantum computations and polynomial advantages for structured, search or approximation problems remain possible.
The best-known quantum optimization methods do not overturn this cautious conclusion. For the Quantum Approximate Optimization Algorithm (QAOA), the workhorse of gate-based quantum optimization, no general scaling advantage is known. Quantum annealing can be exponentially faster on a constructed oracle problem, yet no advantage is established for practical NP-hard instances. Grover search, and its minimum-finding extension, offers a proven quadratic advantage over exhaustive enumeration, not over structure-exploiting classical algorithms.
More promising routes exploit structure directly. Quantum backtracking a nd branch-and-bound provably accelerate structured search trees. The recently published algorithm based on Decoded Quantum Interferometry (DQI) turns Fourier-structured optimization into decoding. For distinct artificial problems, it is superpolynomially faster than known classical algorithms [1]. While it has been beaten for Max-k-XORSAT, DQI has challenged classical solvers given the right problem structure.
An end-to-end reality check
We ran a small benchmark on the symmetric traveling salesperson problem (TSP). We compared the classical optimization solver SCIP on both standard and Quadratic Unconstrained Binary Optimization (QUBO) formulations (SCIP-TSP, SCIP-QUBO), a warm-started QUBO-based QAOA (Penalty QAOA), and a QAOA with permutation-preserving four-qubit exchange mixers (Swap-QAOA) using IBM quantum hardware (ibm_miami with 120 qubits). The details and results are given in Figure 1.
The comparison is unsurprising but instructive. Both classical methods outperform the quantum approaches in both quality and solution time. SCIP on the standard formulation performs best with an optimal solution for 50 cities in under one minute. The QAOA solvers need minutes to terminate; both barely find feasible solutions. Apart from warm starting and custom mixers, our implementations remain close to vanilla QAOA. Thus, performance could be improved by e.g., deeper circuits and error mitigation. Yet this reinforces the practical lesson. Mature classical solvers are close to plug-and-play; competitive quantum performance requires carefully engineering each step of the pipeline.
Where quantum optimization may matter
Does the TSP result make quantum optimization a dead end? No; it changes where we should look. One route is modular: use quantum tree search, amplitude estimation, or quantum optimization inside decomposition, while classical software retains modeling and coordination. The comparison is then against one bottleneck, not an entire solver. The second route targets problems that are richer in structure and solution demand than the regular NP-hard combinatorial optimization problem: multiobjective, robust or stochastic, bilevel, or simulation-based optimization requiring exponentially many outputs or scenario evaluations. For such problems, classical tooling is also less mature.
Multiobjective optimization seeks a potentially exponentially large set of Pareto-optimal trade-offs. In [2], we adapted an existing multiobjective variant of QAOA and incorporated it into a classical multiobjective heuristic, where the outer loop takes over QAOA parameter training. In our experiments using the NSGA-II heuristic, we demonstrated a 10% performance gain in terms of hypervolume and increased stability. Additionally, we were able to increase coverage by up to 40% with little to no hypervolume loss. This shows a promising co-design of quantum sampling and classical search.
In robust optimization, a solution must work across a set of parameter scenarios. In [3], we used the stochastic output of quantum hardware in two approaches applied to use cases from the energy sector with uncertain energy demand: For the unit commitment problem, we solved its deterministic variant with a quantum annealer and ranked near-optimal samples by robustness, producing feasible schedules close to the robust optimum. Further, we trained a QAOA on the expected-value instance of the electric vehicle charging problem and reused the parameters on the scenario-specific circuits. On a simulator, we were able to recover the robust-optimal schedules. These proof-of-concept results suggest a credible role for quantum devices: generating structured candidate sets inside harder problems.
Outlook
The directions outlined above are promising, but none offers a free lunch for quantum advantage. Progress will require tightly integrated and optimized quantum-classical workflows, continued hardware improvements, rigorous theoretical guarantees, and convincing empirical evidence. Yet quantum optimization still rests on only a handful of algorithmic paradigms. Combining insights from quantum physics with classical optimization therefore leaves substantial room for paths toward quantum advantage.
Links:
[L1] https://arxiv.org/search/advanced (query: quant-ph; title or abstract contains the phrase "quantum optimization" in either American or British spelling; first announced January 1 to September 1, 2026; cross-lists included)
References:
[1] S. P. Jordan et al., "Optimization by decoded quantum interferometry," Nature, vol. 646, pp. 831-836, 2025. doi:10.1038/s41586-025-09527-5
[2] I. Turkalj et al., "Enhancing variational quantum algorithms for multicriteria optimization," Quantum Inf. Process., vol. 25, Art. no. 209, 2026. doi:10.1007/s11128-026-05232-y.
[3] P. Halffmann et al., "Harnessing inferior solutions for superior outcomes: obtaining robust solutions from quantum algorithms," in Proc. Genetic Evol. Comput. Conf. Companion (GECCO ’24), 2024, pp. 1950–1953. doi:10.1145/3638530.3664160.
Please contact:
Pascal Halffmann
Fraunhofer Institute for Industrial Mathematics ITWM, Germany