QuCS讲座：加权问题的量子近似优化中的参数设置｜摩根大通应用研究主管Ruslan Shaydulin博士

讲座主题：

Parameter Setting in Quantum Approximate Optimization of Weighted Problems

时间：

美东时间6月08日上午10点30到11点30，北京时间6月08日晚上10点30到11点30

Zoom Link:

https://notredame.zoom.us/j/99013211531?pwd=UW5Wa1ltTEVqY25CczRvUzNhTmQ0dz09

Sign up Mail list：

http://eepurl.com/h5O0Az

讲者：

Ruslan Shaydulin博士，摩根大通全球技术应用研究中心的一名应用研究负责人

主题摘要

量子近似优化算法（QAOA）是在量子计算机上解决组合优化问题的一个主要候选算法。然而，在许多情况下，QAOA需要计算密集的参数优化。在加权问题的情况下，参数优化的挑战尤为突出，因为相位算子的特征值是非整数的，而且QAOA的能量景观也不是周期性的。在这项工作中，我们开发了适用于一般加权问题的QAOA的参数设置启发式方法。首先，我们推导出在不同的权重假设下，深度为p=1的QAOA应用于加权MaxCut问题的最佳参数。特别是，我们严格地证明了传统的智慧，即在平均情况下，第一个接近零的局部最优给出了全局最优的QAOA参数。其次，对于p≥1的情况，我们证明加权MaxCut的QAOA能量景观在参数的简单重构下接近非加权情况。因此，我们可以将以前为非加权MaxCut获得的参数用于加权问题。最后，我们证明，对于p=1，QAOA目标急剧集中在其期望值周围，这意味着我们的参数设置规则对于随机的加权实例来说很有可能成立。我们在34,701个有20个节点的加权图的数据集上对这一方法进行了数值验证，结果表明，使用所提出的固定参数的QAOA能量与使用优化参数的QAOA能量只有1.1个百分点的差距。第三，我们提出了一个受加权MaxCut分析结果启发的通用启发式重构方案，并以QAOA与XY Hamming-weight-preserving mixer应用于组合优化问题为例证明其有效性。我们表明，我们的简单规则改善了局部优化器的收敛性，将达到固定局部最小值所需的迭代次数平均减少了7.2倍。

Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate algorithm for solving combinatorial optimization problems on quantum computers. However, in many cases QAOA requires computationally intensive parameter optimization. The challenge of parameter optimization is particularly acute in the case of weighted problems, for which the eigenvalues of the phase operator are non-integer and the QAOA energy landscape is not periodic. In this work, we develop parameter setting heuristics for QAOA applied to a general class of weighted problems. First, we derive optimal parameters for QAOA with depth p = 1 applied to the weighted MaxCut problem under different assumptions on the weights. In particular, we rigorously prove the conventional wisdom that in the average case the first local optimum near zero gives globally-optimal QAOA parameters. Second, for p ≥ 1 we prove that the QAOA energy landscape for weighted MaxCut approaches that for the unweighted case under a simple rescaling of parameters. Therefore, we can use parameters previously obtained for unweighted MaxCut for weighted problems. Finally, we prove that for p = 1 the QAOA objective sharply concentrates around its expectation, which means that our parameter setting rules hold with high probability for a random weighted instance. We numerically validate this approach on a dataset of 34,701 weighted graphs with up to 20 nodes and show that the QAOA energy with the proposed fixed parameters is only 1.1 percentage points (p.p.) away from that with optimized parameters. Third, we propose a general heuristic rescaling scheme inspired by the analytical results for weighted MaxCut and demonstrate its effectiveness using QAOA with the XY Hamming-weight-preserving mixer applied to the portfolio optimization problem as an example. We show that our simple rule improves the convergence of local optimizers, reducing the number of iterations required to reach a fixed local minimum by 7.2x on average.

关于讲者

Ruslan Shaydulin博士是摩根大通全球技术应用研究中心的一名应用研究负责人。他的研究重心是将量子算法应用于经典问题，重点是优化和机器学习。在加入摩根大通之前，他是美国阿贡国家实验室的Maria Goeppert Mayer研究员。

Ruslan Shaydulin is an Applied Research Lead at the Global Technology Applied Research center at JPMorgan Chase. Ruslan’s research centers on applying quantum algorithms to classical problems, with a focus on optimization and machine learning. Prior to joining JPMorgan Chase, Ruslan was a Maria Goeppert Mayer fellow at Argonne National Laboratory.

关于ND Quantum Computing

ND Quantum Computing 是由美国圣母大学计算机科学与工程系博士生Zhiding Liang与麻省理工学院电子工程与计算机系博士生Hanrui Wang发起的量子计算系列讲座。

Quantum Computer System Lecture Seriess（QuCS）是为没有量子计算背景但对此感兴趣的观众建立基本的量子知识，同时通过邀请量子计算领域的专家来介绍该领域更先进的研究课题。