Quantum Computing Algorithms for Optimization Problems A Study Based on QAOA and MAX-CUT Simulation
Nigeria 
Brunei Darussalam 
Abstract
Quantum computing represents a transformative computational paradigm capable of solving certain
optimization problems more efficiently than classical algorithms. Many real?world applications
including logistics planning, transportation routing, network optimization, and machine learning
involve combinatorial problems whose computational complexity grows exponentially with input size.
This research investigates quantum algorithms for solving optimization problems, with emphasis on
the Quantum Approximate Optimization Algorithm (QAOA), Grover search techniques, and
Hamiltonian?based optimization frameworks. Mathematical formulations are developed for representing
classical optimization problems using quantum Hamiltonians, enabling their implementation in
parameterized quantum circuits. Simulation experiments based on the MAX?CUT problem are conducted to
evaluate algorithm performance. Benchmark comparisons between classical and quantum optimization
approaches demonstrate improved scalability for quantum algorithms in simulated environments. The
results suggest that hybrid quantum?classical optimization methods may offer practical advantages
for solving medium?scale combinatorial problems on near?term quantum hardware.
Keywords: Quantum Computing; QAOA; Combinatorial Optimization; MAX?CUT; Quantum Algorithms; Quantum Annealing
Full text article
References
E. Farhi, J. Goldstone, and S. Gutmann, “A Quantum Approximate Optimization Algorithm,” arXiv preprint arXiv:1411.4028, 2014.
L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 212–219.
T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse Ising model,” Physical Review E, vol. 58, no. 5, pp. 5355–5363, 1998.
J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum, vol. 2, p. 79, 2018.
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information. Cambridge, U.K.: Cambridge University Press, 2010.
A. Montanaro, “Quantum algorithms: An overview,” npj Quantum Information, vol. 2, no. 15023, 2016.
M. Cerezo et al., “Variational quantum algorithms,” Nature Reviews Physics, vol. 3, pp. 625–644, 2021.
K. Bharti et al., “Noisy intermediate-scale quantum algorithms,” Reviews of Modern Physics, vol. 94, no. 1, 2022.
A. Peruzzo et al., “A variational eigenvalue solver on a photonic quantum processor,” Nature Communications, vol. 5, p. 4213, 2014.
J. Biamonte et al., “Quantum machine learning,” Nature, vol. 549, pp. 195–202, 2017.
D. Venturelli et al., “Quantum optimization of fully connected spin glasses,” Physical Review X, vol. 5, no. 3, 2015.
J. R. McClean et al., “The theory of variational hybrid quantum-classical algorithms,” New Journal of Physics, vol. 18, 2016.
A. W. Harrow and A. Montanaro, “Quantum computational supremacy,” Nature, vol. 549, pp. 203–209, 2017.
D. Deutsch, “Quantum theory, the Church–Turing principle and the universal quantum computer,” Proceedings of the Royal Society A, vol. 400, pp. 97–117, 1985.
R. P. Feynman, “Simulating physics with computers,” International Journal of Theoretical Physics, vol. 21, pp. 467–488, 1982.
E. Bernstein and U. Vazirani, “Quantum complexity theory,” SIAM Journal on Computing, vol. 26, no. 5, pp. 1411–1473, 1997.
S. Aaronson, Quantum Computing Since Democritus. Cambridge, U.K.: Cambridge University Press, 2013.
A. Y. Kitaev, “Quantum measurements and the Abelian stabilizer problem,” arXiv preprint quant-ph/9511026, 1995.
A. M. Childs and W. van Dam, “Quantum algorithms for algebraic problems,” Reviews of Modern Physics, vol. 82, pp. 1–52, 2010.
K. Temme et al., “Error mitigation for short-depth quantum circuits,” Physical Review Letters, vol. 119, 2017.
A. Kandala et al., “Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets,” Nature, vol. 549, pp. 242–246, 2017.
P. J. J. O’Malley et al., “Scalable quantum simulation of molecular energies,” Physical Review X, vol. 6, 2016.
R. Somma et al., “Quantum simulations of classical annealing processes,” Physical Review Letters, vol. 101, 2008.
Google AI Quantum, “Hartree–Fock on quantum computers,” Google Quantum AI, 2020.
F. Arute et al., “Quantum supremacy using a programmable superconducting processor,” Nature, vol. 574, pp. 505–510, 2019.
A. Lucas, “Ising formulations of many NP problems,” Frontiers in Physics, vol. 2, p. 5, 2014.
G. Crooks, “Performance of the quantum approximate optimization algorithm on the MAX-CUT problem,” arXiv preprint arXiv:1811.08419, 2018.
S. Hadfield, “Quantum algorithms for scientific computing,” Communications of the ACM, vol. 62, no. 1, pp. 78–87, 2019.
A. Apte et al., “Quantum optimization for integer programming,” Quantum Information Processing, vol. 19, 2020.
K. Blekos et al., “A review on quantum approximate optimization algorithm and its variants,” Physics Reports, vol. 2024.
R. Herrman et al., “Impact of graph structures for QAOA on MAX-CUT,” Quantum Information Processing, vol. 20, 2021.
P. Lotshaw et al., “Scaling quantum optimization algorithms,” IEEE Transactions on Quantum Engineering, vol. 3, 2022.
I. Gaidai et al., “Multi-angle quantum approximate optimization algorithm,” Quantum Information Processing, 2024.
M. Proietti et al., “Measurement-based quantum approximate optimization algorithm,” Physical Review Letters, vol. 130, 2023.
M. Fernández-Pendás et al., “Classical optimizers for variational quantum algorithms,” Quantum Science and Technology, vol. 7, 2022.
Authors
Copyright (c) 2026 Ndiana Okon Asuquo, Siti Mariam
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
