Quantum Annealing for Combinatorial Optimization: Foundations, Architectures, Benchmarks, and Emerging Directions

Abstract

Combinatorial optimization is a foundation of numerous scientific, industrial, and social decision-making questions, but its usefulness is mostly restricted by the exponential complexity of the problem of classical computability. The quantum annealing (QA) has become one of the leading analogue quantum systems to address such problems, whereby optimization problems are converted into physical energy structures and quantum fluctuations are utilized to perform systematic exploration. It provides a critical, synthesized, and comprehensive review of quantum annealing as applied to combinatorial optimization, including the theoretical basis, hardware designs, algorithm methods, issues of embedding and encoding, benchmarking procedures, applications, and integration with quantum algorithms based on gates and solvers on a classical computer. We build a comprehensive taxonomy between adiabatic dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to state-of-the-art flux-qubit annealers, new architectures, and hybrid quantum classical pipelines. We show that the overhead of embedding and encoding and the benchmarking approach taken are the most significant factors in determining scalability and performance, but not the raw number of qubits. Transportation, energy systems, robotics, finance, pharmacological discovery, and machine learning are just some examples of the domain-specific case studies that use QA with minimal empirical utility as a hybrid refinement engine and not an independent solver. Moreover, we introduce a stringent evaluation of the existing benchmarking culture, clarify the causal links between QA and QAOA as well as between VQE and structural predicaments, and reveal the institutional roots of the existing restrictions. We conclude by identifying a research roadmap in the future, focusing on the annealing hardness characterization, Stoquastic control manipulation, embedding rules automation, architecture design, and development of principled quantum advantage. It creates a benchmark reference to those in the field and research and deployment of scalable, reliable, and application-relevant quantum optimization.

Introduction

The text explains quantum annealing (QA) as an advanced optimization method designed to solve complex combinatorial optimization problems, where the number of possible solutions grows exponentially. Traditional optimization methods such as simulated annealing, branch-and-bound, and meta-heuristics struggle with large search spaces and complex constraints. QA addresses these challenges by using quantum mechanics—particularly quantum tunneling—to escape local minima and explore optimal solutions more efficiently.

Optimization problems are typically modeled using Quadratic Unconstrained Binary Optimization (QUBO) or Ising models, where binary variables represent decision choices. In QA, these models are encoded into a quantum system, which evolves toward the lowest-energy state (ground state) that represents the optimal solution.

The document discusses the theoretical foundations of QA, including adiabatic quantum computation, quantum tunneling, spectral gaps, and Hamiltonian evolution. It also compares stoquastic and non-stoquastic Hamiltonians, where non-stoquastic systems may offer stronger theoretical advantages but are harder to simulate and implement.

The hardware landscape of QA includes architectures such as superconducting flux-qubit annealers (e.g., D-Wave systems), the Lechner–Hauke–Zoller (LHZ) architecture, and Rydberg-atom systems. These systems face practical challenges like limited connectivity, noise, decoherence, and embedding constraints that require mapping logical problems onto physical qubits.

Several algorithmic strategies are used to improve QA performance, including adaptive annealing schedules, reverse annealing, pausing strategies, and quantum annealing correction (QAC) for error suppression. Hybrid quantum-classical methods are often applied because current hardware limitations make pure quantum solutions difficult for large problems.

The text highlights the importance of embedding and encoding strategies, such as one-hot, domain-wall, and binary encoding, which affect qubit requirements and hardware efficiency. Benchmarking QA is also discussed, emphasizing the need for fair comparisons with strong classical solvers and realistic problem instances.

QA has been explored in various application domains, including transportation and logistics (routing problems), energy grid optimization, robotics motion planning, financial portfolio optimization, drug discovery, and machine learning tasks such as feature selection and clustering. In many cases, hybrid quantum-classical workflows show promising results, though classical methods still outperform QA in many large-scale applications.

Finally, the text outlines current limitations and future research directions, including improving scalability, reducing noise and embedding overhead, developing non-stoquastic drivers, defining fair benchmarking metrics, and identifying problems where quantum annealing can demonstrate a clear quantum advantage over classical optimization techniques.

Conclusion

The purpose of this review was to combine theory, hardware, algorithms, embedding, benchmarking, applications, ecosystem integration, and prospects to provide an all-inclusive, critical, and unifying synthesis of quantum annealing to solve combinatorial optimization. We prove the problem of quantum annealing to be essentially a physics-based optimization heuristic, and is separate to both classical meta-heuristics and variational quantum algorithms based on gates. Current points of scale are suppressed by embedding and encoding, instead of rawness of qubits. Hybrid workflows are giving the most significant empirical benefits, and not standalone quantum annealing. Unless benchmarking of parity, wall-clock normalization and statistical rigor is available to the assertion, it should be done with caution. The most promising technical directions to overcome a set of limitations are non-stoquastic control, hybrid QA-QAOA integration, and automated embedding. Perhaps most importantly we show that quantum annealing is no longer evaluated in a vacuum but rather than a stack of quantum-classical optimization it should be considered as a stack of physics, algorithms, and engineering inseparably coupled. Quantum annealing is yet to be a universal optimization engine, but it is already a useful scientific tool to investigate the energy landscapes that otherwise can only be explored through computations. The final effect it has will depend not so much on the rate of qubits but on a clever merging with the theory, algorithms, and classical solvers.

References

[1] S. Chowla and H. J. Ryser, “Combinatorial Problems,” Canadian Journal of Mathematics, vol. 2, pp. 93–99, 1950, doi: 10.4153/cjm-1950-009-8. [2] F. Glover, G. Kochenberger, and Y. Du, “Quantum Bridge Analytics I: A Tutorial on Formulating and Using QUBO Models.” [Online]. Available: https://www.nap.edu/catalog/25196/quantum-computing-progress-and-prospects [3] B. A. Cipra, “An Introduction to the Ising Model,” The American Mathematical Monthly, vol. 94, no. 10, pp. 937–959, Dec. 1987, doi: 10.1080/00029890.1987.12000742. [4] T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse Ising model,” 1998. [5] S. Morita and H. Nishimori, “Mathematical foundation of quantum annealing,” J Math Phys, vol. 49, no. 12, 2008, doi: 10.1063/1.2995837. [6] A. Peruzzo et al., “A variational eigenvalue solver on a quantum processor,” Apr. 2013, doi: 10.1038/ncomms5213. [7] E. Farhi, J. Goldstone, and S. Gutmann, “A Quantum Approximate Optimization Algorithm,” Nov. 2014, [Online]. Available: http://arxiv.org/abs/1411.4028 [8] A. Rajak, S. Suzuki, A. Dutta, and B. K. Chakrabarti, “Quantum annealing: An overview,” Jan. 23, 2023, Royal Society Publishing. doi: 10.1098/rsta.2021.0417. [9] R. Barends et al., “Digitized adiabatic quantum computing with a superconducting circuit,” Nature, vol. 534, no. 7606, pp. 222–226, Jun. 2016, doi: 10.1038/nature17658. [10] P. Hauke, H. G. Katzgraber, W. Lechner, H. Nishimori, and W. D. Oliver, “Perspectives of quantum annealing: Methods and implementations,” May 01, 2020, Institute of Physics Publishing. doi: 10.1088/1361-6633/ab85b8. [11] L. P. Yulianti and K. Surendro, “Implementation of Quantum Annealing: A Systematic Review,” 2022, Institute of Electrical and Electronics Engineers Inc. doi: 10.1109/ACCESS.2022.3188117. [12] S. Bravyi, “Monte Carlo simulation of stoquastic Hamiltonians,” Jan. 2015, [Online]. Available: http://arxiv.org/abs/1402.2295 [13] M. Marvian, D. A. Lidar, and I. Hen, “On the computational complexity of curing non-stoquastic Hamiltonians,” Nat Commun, vol. 10, no. 1, Dec. 2019, doi: 10.1038/s41467-019-09501-6. [14] S. Bravyi, D. P. Divincenzo, R. Oliveira, and B. M. Terhal, “The Complexity of Stoquastic Local Hamiltonian Problems,” 2007. [15] W. Vinci and D. A. Lidar, “Non-stoquastic Hamiltonians in quantum annealing via geometric phases,” npj Quantum Inf, vol. 3, no. 1, 2017, doi: 10.1038/S41534-017-0037-Z. [16] A. W. Glaetzle, R. M. W. Van Bijnen, P. Zoller, and W. Lechner, “A coherent quantum annealer with Rydberg atoms,” Nat Commun, vol. 8, Jun. 2017, doi: 10.1038/ncomms15813. [17] F. Leitner and G. B. Mbeng, “Quantum adiabatic brachistochrones for the LHZ architecture,” 2023. [18] H. Zhao, X. Wu, W. Li, X. Fang, and T. Li, “Phase-Slip Based SQUID Used as a Photon Switch in Superconducting Quantum Computation Architectures,” Electronics (Switzerland), vol. 13, no. 12, Jun. 2024, doi: 10.3390/electronics13122380. [19] M. Ohkuwa, H. Nishimori, and D. A. Lidar, “Reverse annealing for the fully connected p -spin model,” Phys Rev A (Coll Park), vol. 98, no. 2, Aug. 2018, doi: 10.1103/PhysRevA.98.022314. [20] M. S. Jattana, “Reverse quantum annealing assisted by forward annealing,” Aug. 2024, doi: 10.3390/quantum6030030. [21] E. J. Crosson and D. A. Lidar, “Prospects for quantum enhancement with diabatic quantum annealing,” Jul. 01, 2021, Springer Nature. doi: 10.1038/s42254-021-00313-6. [22] M. H. Amin et al., “Quantum error mitigation in quantum annealing,” Nov. 2023, [Online]. Available: http://arxiv.org/abs/2311.01306 [23] B. Tasseff et al., “On the emerging potential of quantum annealing hardware for combinatorial optimization,” Journal of Heuristics, vol. 30, no. 5–6, pp. 325–358, Dec. 2024, doi: 10.1007/s10732-024-09530-5. [24] K. L. Pudenz, T. Albash, and D. A. Lidar, “Quantum annealing correction for random Ising problems,” Phys Rev A, vol. 91, no. 4, Apr. 2015, doi: 10.1103/PhysRevA.91.042302. [25] Y. Nambu, “Error correction for encoded quantum annealing revisited,” Jul. 2024, [Online]. Available: http://arxiv.org/abs/2407.15480 [26] C. Ho Thanh, “Hamiltonian Reordering for Shallower Trotterization Circuits.” [Online]. Available: https://github.com/altaris/pauli-coloring-benchmark. [27] R. Acharya et al., “Quantum error correction below the surface code threshold,” Nature, vol. 638, no. 8052, pp. 920–926, Feb. 2025, doi: 10.1038/s41586-024-08449-y. [28] P. Codognet, “Comparing QUBO models for quantum annealing: integer encodings for permutation problems,” International Transactions in Operational Research, vol. 32, no. 1, pp. 18–37, Jan. 2025, doi: 10.1111/itor.13471. [29] M. Kumagai, F. Takano, T. Araki, M. Sato, and H. Kobayashi, “An External Definition of the One-Hot Constraint and Fast QUBO Generation for High-Performance Combinatorial Clustering,” 2021. [Online]. Available: www.ijnc.org, [30] S. Kikuchi, K. Takahashi, and S. Tanaka, “Performance of Domain-Wall Encoding in Digital Ising Machine,” 2025, doi: 10.1109/ACCESS.2023.0322000. [31] P. M. Xavier, Y. Park, D. Noble, I. Santana, M. Paredes, and D. E. Bernal Neira, “A performance comparison of variable encoding techniques for QUIO and QUBO problems.” [32] P. Codognet, “Encoding Binary Comparison Constraints in QUBO for Quantum Annealing,” in GECCO 2025 Companion - Proceedings of the 2025 Genetic and Evolutionary Computation Conference Companion, Association for Computing Machinery, Inc, Aug. 2025, pp. 2419–2423. doi: 10.1145/3712255.3734298. [33] J. Raymond, N. Ndiaye, G. Rayaprolu, and A. D. King, “Improving performance of logical qubits by parameter tuning and topology compensation,” in Proceedings - IEEE International Conference on Quantum Computing and Engineering, QCE 2020, Institute of Electrical and Electronics Engineers Inc., Oct. 2020, pp. 295–305. doi: 10.1109/QCE49297.2020.00044. [34] K. L. Pudenz, T. Albash, and D. A. Lidar, “Error-corrected quantum annealing with hundreds of qubits,” Nat Commun, vol. 5, Feb. 2014, doi: 10.1038/ncomms4243. [35] W. Vinci, T. Albash, G. Paz-Silva, I. Hen, and D. A. Lidar, “Quantum annealing correction with minor embedding,” Phys Rev A, vol. 92, no. 4, Oct. 2015, doi: 10.1103/PhysRevA.92.042310. [36] E. Osaba, E. Villar-Rodriguez, I. Oregi, and A. Moreno-Fernandez-De-Leceta, “Focusing on the hybrid quantum computing - Tabu search algorithm: New results on the Asymmetric Salesman Problem,” in GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion, Association for Computing Machinery, Inc, Jul. 2021, pp. 1476–1482. doi: 10.1145/3449726.3463123. [37] A. N. Ignatov and S. V. Ivanov, “COMPARING THE SOLVERS FOR THE MIXED INTEGER LINEAR PROGRAMMING PROBLEMS AND THE SOFTWARE ENVIRONMENTS THAT CALL THEM,” Bulletin of the South Ural State University, Series: Mathematical Modelling, Programming and Computer Software, vol. 17, no. 3, pp. 57–72, Aug. 2024, doi: 10.14529/mmp240305. [38] M. Gou et al., “Hierarchical Quantum Optimization via Backbone-Driven Problem Decomposition: Integrating Tabu-Search with QAOA,” Apr. 2025, [Online]. Available: http://arxiv.org/abs/2504.09575 [39] V. Tomar, M. Bansal, and P. Singh, “Metaheuristic Algorithms for Optimization: A Brief Review,” Engineering Proceedings, vol. 59, no. 1, 2023, doi: 10.3390/engproc2023059238. [40] A. Bonomi, T. De Min, E. Zardini, E. Blanzieri, V. Cavecchia, and D. Pastorello, “Quantum Annealing Learning Search Implementations,” Dec. 2022, doi: 10.26421/QIC22.3-4-1. [41] S. Mario et al., “Quantum Annealing based Hybrid Strategies for Real Time Route Optimization.” [42] E. W. H. Chow, G. T. S. Ho, V. Tang, and M. M. F. Tam, “Utilizing Quantum Annealing to Address Vehicle Routing Challenges in Cold Chain Logistics,” Association for Computing Machinery (ACM), Apr. 2025, pp. 137–142. doi: 10.1145/3760622.3760626. [43] “ENHANCING ROBOTIC MANIPULATION THROUGH FULLY INTEGRATED QUANTUM ANNEALING: THE FIQA-RM SYSTEM.” [44] S. N. Morapakula, S. Deshpande, R. Yata, R. Ubale, U. Wad, and K. Ikeda, “End-to-End Portfolio Optimization with Quantum Annealing,” Apr. 2025, [Online]. Available: http://arxiv.org/abs/2504.08843 [45] C. Pomeroy, A. Pramov, K. Thakrar, and L. Yendapalli, “Quantum Annealing for Machine Learning: Applications in Feature Selection, Instance Selection, and Clustering Notebook for the QuantumCLEF Lab at CLEF 2025,” 2025. [Online]. Available: https://github.com/dsgt-arc/ [46] E. Pelofske, A. Bärtschi, and S. Eidenbenz, “Short-depth QAOA circuits and quantum annealing on higher-order ising models,” npj Quantum Inf, vol. 10, no. 1, Dec. 2024, doi: 10.1038/s41534-024-00825-w. [47] J. Li, “Knowledge Distillation Inspired Variational Quantum Eigensolver with Virtual Annealing,” May 2025, [Online]. Available: http://arxiv.org/abs/2505.03998 [48] F. A. Quinton, P. A. S. Myhr, M. Barani, P. Crespo del Granado, and H. Zhang, “Quantum annealing applications, challenges and limitations for optimisation problems compared to classical solvers,” Sci Rep, vol. 15, no. 1, Dec. 2025, doi: 10.1038/s41598-025-96220-2. [49] V. Choi, “Limitation of Stoquastic Quantum Annealing: A Structural Perspective,” Sep. 2025, [Online]. Available: http://arxiv.org/abs/2509.16265

Copyright

Copyright © 2026 Rudraksh Sharma, Ravi Katukam, Arjun Nagulapally. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.