Optimization Algorithms for Combinatorial Problems: A Comparative Study of Quantum Annealing and Classical Methods
Keywords:
Combinatorial optimization, quantum annealing, classical optimization algorithms, simulated annealing, genetic algo-rithms, branch-and-bound, traveling salesman problem, graph partitioning, quantum computing.Abstract
Optimization algorithms for combinatorial problems play a critical role in a wide range of applications, from logistics and scheduling to cryptography and artificial intelligence. Traditional classical methods, such as simulated annealing, genetic algorithms, and branch-and-bound techniques, have been widely employed to solve these problems, but they often face limitations in terms of computational efficiency and scalability as problem complexity grows. In recent years, quantum computing has emerged as a promising alternative, with quantum annealing offering a novel approach to solving combinatorial optimization problems. This study provides a comparative analysis of quantum annealing and classical optimization methods, highlighting their respective strengths and limitations. We explore how quantum annealing, through leveraging quantum tunnelling and superposition, has the potential to outperform classical algorithms in specific problem domains and Noisy Mean Field Annealing (NMFA) is used to comparisons of all algorithms. Benchmarking various combinatorial problems, such as the Traveling Salesman Problem (TSP), Max-Cut, Knapsack, and Quadratic Assignment Problem (QAP), this paper discusses performance metrics, computational time, and scalability. The findings suggest that while classical methods remain robust and practical for many real-world problems, quantum annealing holds significant promise, especially as quantum hardware continues to mature. However, there remain challenges in terms of noise, coherence, and problem mapping, which currently limit the full realization of quantum annealing's potential. This study offers insights into the future directions of optimization techniques and the evolving role of quantum computing in solving complex combinatorial problems.
Downloads
References
Boixo, S. et al. Evidence for quantum annealing with more than one hundred qubits. Nature phys-ics 10, 218–224 (2014).
Inagaki, T. et al. A coherent ising machine for 2000-node optimization problems. Science 354, 603–606 (2016).
Lambora, A., Gupta, K., & Chopra, K. (2019, February). Genetic algorithm-A literature review. In 2019 international conference on machine learning, big data, cloud and parallel computing (COMITCon) (pp. 380-384). IEEE.
Poulsen, P. N., & Olesen, J. F. Uniqueness of Fi-nite Element Limit Analysis solutions based on weak form lower and upper bound meth-ods. International Journal of Solids and Struc-tures, 286, 112532.
Leleu, T., Yamamoto, Y., Utsunomiya, S. & Aiha-ra, K. Combinatorial optimization using dynam-ical phase transitions in driven-dissipative sys-tems. Physical Review E 95, 022118 (2017).
Rosenberg, G. et al. Solving the optimal trading trajectory problem using a quantum annealer. IEEE Journal of Selected Topics in Signal Pro-cessing 10, 1053–1060 (2016).
Crawford, D., Levit, A., Ghadermarzy, N., Oberoi, J. S. & Ronagh, P. Reinforcement learning using quantum boltzmann machines.Quantum Inf. Comput. 18, 51–74 (2018).
Siarry, P.Metaheuristics (Springer, 2016).
Arora, S. & Barak, B.Computational Complexity - A Modern Approach (Cambridge University Press, 2009).
Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. Op-timization by simulated annealing. science 220, 671–680 (1983).
Bilbro, G. L. et al. Optimization by mean field annealing. In Touretzky, D. S. (ed.) Advances in Neural Information Processing Systems 1,[NIPS Conference, Denver, Colorado, USA, 1988], 91–98 (Morgan Kaufmann, 1988).
Goemans, M. X. & Williamson, D. P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite pro-gramming. JACM 42, 1115–1145 (1995).
Smith, K. A. Neural networks for combinatorial optimization: a review of more than a decade of research. INFORMS J. Comput. 11,15–34 (1999).
Lucas, A. Ising formulations of many np prob-lems. Front. Phys. 2,5 (2014).
Johnson, M. W. et al. Quantum annealing with manufactured spins. Nature 473, 194–198 (2011).
Bunyk, P. I. et al. Architectural considerations in the design of a superconducting quantum anneal-ing processor. IEEE Transactions on Applied Su-perconductivity 24, 1–10 (2014).
Boixo, S. et al. Evidence for quantum annealing with more than one hundred qubits. Nature phys-ics 10, 218–224 (2014).
Boev, A. S. et al. Quantum-inspired optimization for wavelength assignment. Frontiers in Physics 10, 1092065 (2023).
Marandi, A., Wang, Z., Takata, K., Byer, R. L. & Yamamoto, Y. Network of time-multiplexed opti-cal parametric oscillators as a coherent ising ma-chine. Nature Photonics 8, 937–942 (2014).
Inagaki, T. et al. A coherent ising machine for 2000-node optimization problems. Science 354, 603–606 (2016).
McMahon, P. L. et al. A fully programmable 100-spin coherent ising machine with all-to-all con-nections. Science 354,614–617 (2016).
Singha, A. K., Tiwari, P. K., Shukla, N., & Yadav, G. Transformative Trends: Analyzing the Inte-gration of Block chain in Banking Opera-tions.https://themultiphysicsjournal.com/index.php/ijm/article/view/1589
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.
IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.
