Centre for High Performance Computing 2025 National Conference

COMPARISON OF QUANTUM ALGORITHMS FOR QUADRATIC OPTIMIZATION

1 Dec 2025, 11:40

20m

1/1-7 - Room 7 (Century City Conference Centre)

Talk Quantum Computing Special

Speaker

Ms Helarie Rose Medie Fah (UKZN)

Description

Optimization problems appear widely in science and industry, yet their classical solutions often demand considerable computational resources. Quantum computing provides a promising framework for addressing such problems more efficiently by exploiting quantum superposition and entanglement [1]. In this work, we investigate several quantum gradient descent [2] approaches to find the minimum of a quadratic cost function. Performing the implementation through Amplitude encoding, we begin by a quantum gradient descent algorithm with a phase estimation-based method. To further enhance performance, we develop and test additional strategies, including linear combination of unitaries (LCUs) [3], the Sz.-Nagy dilation method [4], and a so-called unitary selection method, where the cost function is explicitly defined as a quadratic function. These methods are evaluated in terms of circuit depth, number of iterations, and accuracy. Our results show that the unitary selection outperforms phase estimation, LCUs provide a further improvement, and the Sz.-Nagy approach achieves the highest efficiency among all tested methods. This comparative study highlights the potential of pure quantum algorithms in solving real-world quadratic optimization problems.

[1] Nielsen, M. A., & Chuang, I. L., Quantum Computation and Quantum Information (10th Anniversary Edition, 2010), Cambridge University Press.

[2] Rebentrost, P., Schuld, M., Wossnig, L., Petruccione, F., and Lloyd, S., Quantum gradient descent and Newton’s method for constrained polynomial optimization, New J. Phys., 21(7):073023, (2019).

[3] Chakraborty, Shantanav. "Implementing any linear combination of unitaries on intermediate-term quantum computers." Quantum 8 (2024): 1496.

[4] Gaikwad, Akshay, Arvind, and Kavita Dorai. "Simulating open quantum dynamics on an NMR quantum processor using the Sz.-Nagy dilation algorithm." Physical Review A 106.2 (2022): 022424.