Comparative Analysis of Hamilton Construction Methods for the Quantum Approximate Optimization Algorithm

Abstract

Quantum computing has the potential to revolutionize the solution of complex optimization problems. Quantum approximate optimization algorithm (QAOA) is one of the most prominent methods in this field. This study compares two different approaches to Hamiltonian construction within the context of QAOA. Specifically, it focuses on the weighted bipartite graph matching problem. The first approach employs the penalty method, which increases the objective function when constraints are violated. The second approach is based on Hadfield’s Boolean representation, which constructs Hamiltonians directly from constraints expressed as Boolean functions. The results obtained indicate that the Hamiltonian constructed using Hadfield’s method demonstrates a more effective performance in reaching optimal outcomes. This finding underscores the potential of Hadfield’s method in constrained combinatorial optimization problems.

Keywords

• QAOA
• Hamiltonian
• weighted bipartite graph
• matching problem
• penalty method

Kuantum Yaklaşık Optimizasyon Algoritması İçin Hamilton İşlemcisi İnşası Yöntemlerinin Karşılaştırmalı Analizi

Abstract

Kuantum hesaplama, karmaşık optimizasyon problemlerini çözmede devrim niteliğinde bir potansiyele sahiptir. Kuantum yaklaşık optimizasyon algoritması (QAOA), bu alandaki en önemli yöntemlerden biridir. Çalışma özellikle iki parçalı ağırlıklı graf eşleştirme problemine odaklanmaktadır. İlk yaklaşım, kısıtların ihlal edilmesi durumunda amaç fonksiyonunu artıran ceza yöntemini kullanmaktadır. İlk yaklaşım, kısıtlar ihlal edildiğinde amaç fonksiyonunu artıran ceza yöntemini kullanmaktadır. İkinci yaklaşım ise, kısıtları doğrudan Boolean fonksiyonları olarak ifade ederek Hamilton işlemcisi oluşturan Hadfield’ın Boolean temsiline dayanmaktadır. Elde edilen sonuçlar, Hadfield’ın Boolean temsili kullanılarak inşa edilen Hamilton işlemcisinin optimal sonuca ulaşma açısından daha etkili bir performans sergilediğini göstermektedir. Bu bulgu, kısıtlı kombinatorik optimizasyon problemlerinde Hadfield’ın Boolean temsil yönteminin potansiyelini vurgulamaktadır.

Keywords

• QAOA
• Hamilton işlemcisi
• iki parçalı graf
• eşleştirme problemi
• ceza yöntemi

References

1. Farhi, E., Goldstone, J., & Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028.
2. Preskill, J. (2018). Quantum computing in the NISQ era and beyond. Quantum, 2, 79.
3. Born, M., & Fock, V. (1928). Beweis des adiabatensatzes. Zeitschrift für Physik, 51(3), 167–180.
4. Hadfield, S., et al. (2019). From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12(2), 34.
5. Golden, J., Bärtschi, A., O’Malley, D., & Eidenbenz, S. (2021). Threshold-based quantum optimization. 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), 137–147.
6. Sack, S. H., & Serbyn, M. (2021). Quantum annealing initialization of the quantum approximate optimization algorithm. Quantum, 5, 491.
7. Zhu, L., et al. (2022). Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer. Physical Review Research, 4(3), 033029.
8. Bakó, B., Glos, A., Salehi, Ö., & Zimborás, Z. (2025). Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs. Quantum, 9, 1663.

9. Hastings, M. B. (2019). Classical and quantum bounded depth approximation algorithms. arXiv preprint arXiv:1905.07047.
10. Morales, M. E. S., Biamonte, J. D., & Zimborás, Z. (2020). On the universality of the quantum approximate optimization algorithm. Quantum Information Processing, 19, 1–26.
11. Farhi, E., Gamarnik, D., & Gutmann, S. (2020). The quantum approximate optimization algorithm needs to see the whole graph: A typical case. arXiv preprint arXiv:2004.09002.
12. Blekos, K., et al. (2024). A review on quantum approximate optimization algorithm and its variants. Physics Reports, 1068, 1–66.
13. Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in Physics, 2, 5.
14. Glover, F., Kochenberger, G., & Du, Y. (2018). A tutorial on formulating and using QUBO models. arXiv preprint arXiv:1811.11538.
15. Rosenberg, I. G. (1975). Reduction of Bivalent Maximization to the Quadratic Case.
16. Hadfield, S. (2021). On the representation of Boolean and real functions as Hamiltonians for quantum computing. ACM Transactions on Quantum Computing, 2(4), 1–21.
17. Montgomery, R. J. (2016). Kidney paired donation: Optimal and equitable matchings in bipartite graphs. Rose-Hulman Undergraduate Mathematics Journal, 17(1), 11.
18. Kesselheim, T., Radke, K., Tönnis, A., & Vöcking, B. (2013). An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. European Symposium on Algorithms, 589–600.
19. Mehta, A., et al. (2013). Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 8(4), 265–368.
20. Graver, J. E. (1975). On the foundations of linear and integer linear programming I. Mathematical Programming, 9(1), 207–226.
21. Salehi, Ö., Glos, A., & Miszczak, J. A. (2022). Unconstrained binary models of the travelling salesman problem variants for quantum optimization. Quantum Information Processing, 21(2), 67.
22. Gonzalez-Bermejo, S., Alonso-Linaje, G., & Atchade-Adelomou, P. (2022). GPS: A new TSP formulation for its generalizations type QUBO. Mathematics, 10(3), 416.
23. Zhang, J., Bianco, G., & Beck, J. (2022). Solving job-shop scheduling problems with QUBO-based specialized hardware. Proceedings of the International Conference on Automated Planning and Scheduling, 32.
24. Domino, K., Kundu, A., Salehi, Ö., & Krawiec, K. (2022). Quadratic and higher-order unconstrained binary optimization of railway rescheduling for quantum computing. Quantum Information Processing, 21(9), 337.
25. Arya, A., Botelho, L., Cañete, F., Kapadia, D., & Salehi, Ö. (2022). Applications of quantum annealing to music theory. In Quantum Computer Music: Foundations, Methods and Advanced Concepts, Springer, 373–406.
26. Nüßlein, J., Gabor, T., Linnhoff-Popien, C., & Feld, S. (2022). Algorithmic QUBO formulations for k-SAT and hamiltonian cycles. Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2240–2246.
27. Kirkpatrick, S., Gelatt Jr, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680.
28. Dorigo, M., Birattari, M., & Stutzle, T. (2006). Ant colony optimization. IEEE Computational Intelligence Magazine, 1(4), 28–39.
29. Kadowaki, T., & Nishimori, H. (1998). Quantum annealing in the transverse Ising model. Physical Review E, 58(5), 5355.
30. Crooks, G. E. (2018). Performance of the quantum approximate optimization algorithm on the maximum cut problem. arXiv preprint arXiv:1811.08419.
31. Glos, A., Krawiec, A., & Zimborás, Z. (2022). Space-efficient binary optimization for variational quantum computing. npj Quantum Information, 8(1), 39.
32. de la Grand’rive, P. D., & Hullo, J.-F. (2019). Knapsack problem variants of QAOA for battery revenue optimisation. arXiv preprint arXiv:1908.02210.
33. Bakó, B., Glos, A., Salehi, Ö., & Zimborás, Z. (2022). Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs. arXiv preprint arXiv:2209.03386.
34. Herrman, R., Lotshaw, P. C., Ostrowski, J., Humble, T. S., & Siopsis, G. (2022). Multi-angle quantum approximate optimization algorithm. Scientific Reports, 12(1), 6781.
35. Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1–2), 83–97.
36. Edmonds, J., & Karp, R. M. (1972). Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM), 19(2), 248–264.
37. Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM), 34(3), 596–615.
38. Kaplan, H., Naori, D., & Raz, D. (2022). Online weighted matching with a sample. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1247–1272.
39. Fahrbach, M., Huang, Z., Tao, R., & Zadimoghaddam, M. (2022). Edge-weighted online bipartite matching. Journal of the ACM, 69(6), 1–35.
40. Valencia, C. E., & Vargas, M. C. (2016). Optimum matchings in weighted bipartite graphs. Boletín de la Sociedad Matemática Mexicana, 22, 1–12.
41. Fernández-Pendás, M., Combarro, E. F., Vallecorsa, S., Ranilla, J., & Rúa, I. F. (2022). A study of the performance of classical minimizers in the quantum approximate optimization algorithm. Journal of Computational and Applied Mathematics, 404, 113388.