Evolving objective function for improved variational quantum optimization
Evolving objective function for improved variational quantum optimization
复制标题
DOI：
10.1103/physrevresearch.4.023225
复制
发表时间：
2021-05
影响因子：
4.2
通讯作者：
Ioannis Kolotouros;P. Wallden
中科院分区：
文献类型：
--
作者：
Ioannis Kolotouros;P. Wallden
利用变分量子算法解决优化问题是实现有用的计算量子优势的一个有前途的方法。保证算法在短时间内以高概率收敛到接近最优解是保证算法性能的关键。在Barkoutsos等人（Quantum 2020）中，引入了另一类目标函数，称为条件风险值（CVaR），并证明它们比标准目标函数表现更好。在这里，我们通过引入一个进化的目标函数来扩展这项工作，我们称之为上升cvar，它可以用于任何优化问题。我们在仿真环境中测试了我们提出的目标函数，使用三个不同的优化问题作为案例研究：Max-Cut， Number Partitioning和Portfolio optimization。我们研究了不同大小的多个实例，并使用具有硬件高效ansatz和量子近似优化算法（QAOA）的变分量子特征求解器（VQE）分析了性能。我们表明，在所有情况下，上升CVaR都比标准目标函数或Barkoutsos等人（Quantum 2020）的“常数”CVaR表现得更好，并且它可以用作避免次优最小值的启发式。我们的建议在所有问题中都实现了与理想状态的更高重叠，无论我们考虑的是简单的还是困难的实例——平均而言，它在组合优化和数字划分方面提供了高达10倍的重叠，而在Max-Cut方面提供了80%的改进。在我们考虑的困难情况下，对于数字划分问题，标准目标函数几乎在所有情况下都不能找到正确的解，CVaR在60%的情况下找到了正确的解，而上升-CVaR在95%的情况下找到了正确的解。
A promising approach to useful computational quantum advantage is to use variational quantum algorithms for optimisation problems. Crucial for the performance of these algorithms is to ensure that the algorithm converges with high probability to a near-optimal solution in a small time. In Barkoutsos et al (Quantum 2020) an alternative class of objective functions, called Conditional Value-at-Risk (CVaR), was introduced and it was shown that they perform better than standard objective functions. Here we extend that work by introducing an evolving objective function, which we call Ascending-CVaR and that can be used for any optimisation problem. We test our proposed objective function, in an emulation environment, using as case-studies three different optimisation problems: Max-Cut, Number Partitioning and Portfolio Optimisation. We examine multiple instances of different sizes and analyse the performance using the Variational Quantum Eigensolver (VQE) with hardware-efficient ansatz and the Quantum Approximate Optimization Algorithm (QAOA). We show that Ascending-CVaR in all cases performs better than standard objective functions or the"constant"CVaR of Barkoutsos et al (Quantum 2020) and that it can be used as a heuristic for avoiding sub-optimal minima. Our proposal achieves higher overlap with the ideal state in all problems, whether we consider easy or hard instances -- on average it gives up to ten times greater overlap at Portfolio Optimisation and Number Partitioning, while it gives an 80% improvement at Max-Cut. In the hard instances we consider, for the number partitioning problem, standard objective functions fail to find the correct solution in almost all cases, CVaR finds the correct solution at 60% of the cases, while Ascending-CVaR finds the correct solution in 95% of the cases.