Pushing the Limits of Quantum Computing: Variational Algorithms for Solving NP-Hard Problems
DOI:
https://doi.org/10.61536/ambidextrous.v5i02.300Keywords:
Quantum Computing; Variational Algorithms; NP-Hard Problems; Maxbisection; Hybrid OptimizationAbstract
This study explores the application of variational quantum algorithms to solve NP-hard combinatorial optimization problems, focusing specifically on the MaxBisection problem. The research introduces an enhanced hybrid quantum-classical framework, HTAAC-QSDP, which combines problem-informed ansatz design with semidefinite programming (SDP) relaxation and iterative optimization. Simulation results across multiple graph instances show that the proposed method achieves approximation ratios consistently above 0.95, approaching classical SDP benchmarks. Experiments also demonstrate the sensitivity of performance to key hyperparameters such as circuit depth, rotation scaling, and learning rate. Additionally, hardware implementation on IBM quantum devices reveals the model’s resilience under noise, provided that initialization and optimization strategies are carefully tuned. The findings suggest that variational quantum approaches can provide high-quality approximations for complex NP-hard problems, even in the noisy intermediate-scale quantum (NISQ) era. The results lay the groundwork for scalable quantum optimization frameworks and support the advancement of quantum advantage in real-world applications.
Downloads
References
Aaronson, S. (2020). Quantum computing and the limits of the efficient computability. Communications of the ACM, 63(5), 86–94. https://doi.org/10.1145/3375636
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., ... & Aspuru-Guzik, A. (2022). Noisy intermediate-scale quantum algorithms. Reviews of Modern Physics, 94(1), 015004. https://doi.org/10.1103/RevModPhys.94.015004
Brandão, F. G. S. L., & Svore, K. M. (2017). Quantum speed-ups for semidefinite programming. Proceedings of the 58th IEEE Symposium on Foundations of Computer Science, 415–426. https://doi.org/10.1109/FOCS.2017.45
Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., ... & Coles, P. J. (2021). Variational quantum algorithms. Nature Reviews Physics, 3(9), 625–644. https://doi.org/10.1038/s42254-021-00348-9
Farhi, E., Goldstone, J., & Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028.
Huang, H. Y., Broughton, M., Mohseni, M., Babbush, R., Kueng, R., & Preskill, J. (2022). Quantum advantage in learning from experiments. Nature, 603(7902), 146–150. https://doi.org/10.1038/s41586-021-04351-1
Jain, A., & Radhakrishnan, J. (2020). Quantum algorithms for NP-hard problems: A review. Quantum Information Processing, 19(12), 1–30. https://doi.org/10.1007/s11128-020-02927-3
McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R., & Neven, H. (2016). Theory of variational quantum simulation. New Journal of Physics, 18(2), 023023. https://doi.org/10.1088/1367-2630/18/2/023023
Moll, N., Barkoutsos, P., Bishop, L. S., Chow, J. M., Cross, A., Egger, D. J., ... & Gambetta, J. M. (2018). Quantum optimization using variational algorithms on near-term quantum devices. Quantum Science and Technology, 3(3), 030503. https://doi.org/10.1088/2058-9565/aab822
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M. H., Zhou, X. Q., Love, P. J., ... & O’Brien, J. L. (2014). A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5, 4213. https://doi.org/10.1038/ncomms5213
Preskill, J. (2018). Quantum computing in the NISQ era and beyond. Quantum, 2, 79. https://doi.org/10.22331/q-2018-08-06-79
Rattew, A., Zhu, L., Cui, S., Ostaszewski, M., & Leung, N. (2021). A domain-agnostic, noise-aware circuit learning strategy for near-term quantum applications. npj Quantum Information, 7(1), 1–9. https://doi.org/10.1038/s41534-021-00443-2
Wang, S., Hadfield, S., Jiang, Z., & Rieffel, E. G. (2018). Quantum approximate optimization algorithm for MaxCut: A fermionic view. Physical Review A, 97(2), 022304. https://doi.org/10.1103/PhysRevA.97.022304
Yamamoto, N., & Onodera, T. (2021). Hybrid quantum-classical optimization with reparameterization. npj Quantum Information, 7, 116. https://doi.org/10.1038/s41534-021-00461-0
Zhou, L., Wang, S. T., Choi, S., Pichler, H., & Lukin, M. D. (2020). Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X, 10(2), 021067. https://doi.org/10.1103/PhysRevX.10.021067.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Austin Wenxuan Li, Lilis Stianingsih, Ana Utami Zainal
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
