Quantum Optimization for Enhanced Combinatorial Algorithms
DOI:
https://doi.org/10.71330/thenucleus.2025.1453Abstract
The twenty-first century has been the era of data. Algorithms are crucial in tasks ranging from simple document searches to complex batching and scheduling jobs. Optimization techniques are often applied to enhance algorithms and achieve better results. As Moore rightly predicted, the exponential increase in transistors has led to a point where classical computers can no longer solve specific problems within a human timeframe. This paved the way for the development of quantum computers, which utilize quantum phenomena to solve problems. Quantum optimization techniques and algorithms have been designed to leverage the quantum advantage for improved optimization. This research compares and presents the results of quantum optimization techniques applied to classic combinatorial algorithms.
References
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information. Cambridge, U.K.: Cambridge Univ. Press, 2010.
R. P. Feynman, "Simulating physics with computers," Int. J. Theor. Phys., vol. 21, no. 6–7, pp. 467–488, 1982.
J. Preskill, "Quantum computing in the NISQ era and beyond," Quantum, vol. 2, p. 79, 2018.
C. H. Bennett and D. P. DiVincenzo, "Quantum information and computation," Nature, vol. 404, no. 6775, pp. 247–255, 2000.
P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," SIAM J. Comput., vol. 26, no. 5, pp. 1484–1509, 1997.
L. K. Grover, "A fast quantum mechanical algorithm for database search," in Proc. 28th Annu. ACM Symp. Theory Comput. (STOC), 1996, pp. 212–219.
F. Arute et al., "Quantum supremacy using a programmable superconducting processor," Nature, vol. 574, no. 7779, pp. 505–510, 2019.
S. J. Devitt, W. J. Munro, and K. Nemoto, "Quantum error correction for beginners," Rep. Prog. Phys., vol. 76, no. 7, p. 076001, 2013.
M. Kjaergaard, M. E. Schwartz, J. Braumüller, P. Krantz, J. I. J. Wang, S. Gustavsson, and W. D. Oliver, "Superconducting qubits: Current state of play," Annu. Rev. Condens. Matter Phys., vol. 11, pp. 369–395, 2020.
J. Liu, D. An, D. Fang, J. Wang, G. H. Low, and S. P. Jordan, "Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation," Commun. Math. Phys., vol. 404, no. 2, pp. 963–1020, 2023.
A. Lucas, "Ising formulations of many NP problems," Front. Phys., vol. 2, no. 1, pp. 5–17, 2014.
T. Kadowaki and H. Nishimori, "Quantum annealing in the transverse Ising model," Phys. Rev. E, vol. 58, no. 5, pp. 5355–5363, 1998.
S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi, "Optimization by simulated annealing," Science, vol. 220, no. 4598, pp. 671–680, 1983.
F. Glover and M. Laguna, "Tabu search," Kluwer Acad. Publ., vol. 1, no. 1, pp. 1–32, 1997.
D. S. Johnson, "The NP-completeness column: An ongoing guide," J. Algorithms, vol. 3, no. 2, pp. 182–195, 1982.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 The Nucleus
This work is licensed under a Creative Commons Attribution 4.0 International License.
For all articles published in The Nucleus, copyright is retained by the authors. Articles are licensed under an open access licence [CC Attribution 4.0] meaning that anyone may download and read the paper for free. In addition, the article may be reused and quoted provided that the original published version is cited properly.
