中文摘要：

该文用量子近似动态规划解大规模机组组合问题。利用量子叠加态可表示海量信息的特性,把大规模的0-1机组组合状态用量子叠加态表示,将量子旋转门作为量子叠加态的搜索策略,实现了近似动态规划对海量机组组合状态空间的全局搜索。使用量子测量塌缩原理解Bellman方程,提高了方程的求解效率。用量子平均收敛概率改进迭代中断条件,避免了算法的过度迭代。10~1000机系统的计算结果表明：该文算法能有效地搜索大规模状态空间,产生解Bellman方程所必须的预决策状态;可在多项式时间内获取高质量的解,与外–内逼近法相比最优值的平均偏差小于1/100;所解系统的规模较传统动态规划法增加10倍以上,克服了＂维数灾＂问题。用量子计算理论克服近似动态规划遇到的状态空间搜索难等问题是可行的,算法具有广阔的应用前景。

英文摘要：

The quantum inspired approximate dynamic programming （QI-ADP） algorithm was applied to solve the large-scale unit commitment （UC） problems. The large numbers of 0-1 states in the large-scale UC problem were expressed with the quantum superposition state effectively by means of its ability in storing massive information. Using the quantum rotation gate as the search strategy for the quantum superposition state, the QI-ADP algorithm implemented the global search in the space of the massive states of the UC problem. Meanwhile, the principle of the quantum collapsing was applied to solve the Bellman equation with a higher efficiency. To avoid the over-iteration, the average convergence probability was used to improve the iteration interrupt condition of the QI-ADP algorithm. The calculated results of the test systems from 10 units to 1000 units show that the QI-ADP algorithm can efficiently search in the space of large-scale states to generate the necessary pre-decision states for solving the Bellman equation. Furthermore, the QI-ADP algorithm can obtain the high-quality solutions within a polynomial time. The ave＇rage deviations of the optimal values between the QI-ADP and the outer-inner approximation approach are less than 1%. On the other hand, the QI-ADP algorithm can solve large-scale UC problems successfully, and the size of the UC problems is over 10 times larger than that by using the classic dynamic programming. Moreover, the QI-ADP algorithm has overcome the problem of ＂curse of dimensionality＂. Therefore, it is feasible using the principle of quantum computing to overcome some practical disadvantages in ADP, such as the difficulty of searching in the state space. Consequently, the QI-ADP algorithm has very broad application prospects.