He Jianhao, Li Lüzhou. An Overview of Quantum Optimization[J]. Journal of Computer Research and Development, 2021, 58(9): 1823-1834. DOI: 10.7544/issn1000-1239.2021.20210276
Citation:
He Jianhao, Li Lüzhou. An Overview of Quantum Optimization[J]. Journal of Computer Research and Development, 2021, 58(9): 1823-1834. DOI: 10.7544/issn1000-1239.2021.20210276
He Jianhao, Li Lüzhou. An Overview of Quantum Optimization[J]. Journal of Computer Research and Development, 2021, 58(9): 1823-1834. DOI: 10.7544/issn1000-1239.2021.20210276
Citation:
He Jianhao, Li Lüzhou. An Overview of Quantum Optimization[J]. Journal of Computer Research and Development, 2021, 58(9): 1823-1834. DOI: 10.7544/issn1000-1239.2021.20210276
(School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006)
Funds: This work was supported by the National Natural Science Foundation of China (61772565), the Basic and Applied Basic Research Foundation of Guangdong Province (2020B1515020050), and the Key Research and Development Project of Guangdong Province (2018B030325001).
Quantum optimization has attracted much attention in recent years. It mainly studies how to accelerate the solution of optimization problems with quantum computing. This overview will classify the quantum optimization algorithm according to whether the optimization variable is continuous, and focus on introducing the continuous variable optimization algorithm. Through the investigation of existing work, this article obtains the following observations: 1)The works of discrete variable quantum optimization were distributed five years ago, while the works of continuous variable quantum optimization has attracted more attention in the last five years; 2)The main basic technologies used in quantum optimization were mainly proposed ten to twenty years ago, and basic innovations are needed; 3)In most works of quantum optimization, theoretical acceleration of time complexity or query complexity is achieved, but more rigorous theoretical analysis is still needed; 4)There are still many problems worthy of exploration by quantum computing researchers in the optimization field, especially in the field of non-convex optimization, which is considered to be difficult in classical computing.