ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2021, Vol. 58 ›› Issue (9): 1823-1834.doi: 10.7544/issn1000-1239.2021.20210276

Special Issue: 2021量子计算专题

Previous Articles     Next Articles

An Overview of Quantum Optimization

He Jianhao Li Lüzhou   

  1. (School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006)
  • Online:2021-09-01
  • Supported by: 
    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).

Abstract: 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.

Key words: quantum computing, quantum optimization, mathematical programming, discrete variable optimization, continuous variable optimization

CLC Number: