Speaker
Triscia Mundo
(Singapore University of Technology and Design)
Description
It is well known that globally optimizing the training objectives of Variational Quantum Algorithms (VQAs) is $\mathsf{NP}$-hard. This motivates the use of local optimization methods in practice, raising the question of whether finding locally optimal parameters is computationally easier. We show that it is not: finding a local optimum for VQA training is also $\mathsf{NP}$-hard. Our proof proceeds by establishing a bridge between polynomial optimization and VQA training, exploiting the connection between VQA objective functions and Hermitian trigonometric polynomials.
| Topic | Theoretical foundations of quantum learning |
|---|
Authors
Dax Enshan Koh
(A*STAR QInC, Singapore Institute of Technology, Singapore University of Technology and Design)
Triscia Mundo
(Singapore University of Technology and Design)
Iosif Sakos
(Singapore University of Technology and Design)
Antonios Varvitsiotis
(Singapore University of Technology and Design, Centre for Quantum Technologies, Archimedes Research Unit on AI, Data Science and Algorithms)