论文标题
用局部自旋算法对Maxcut进行近似优化
Approximate optimization of MAXCUT with a local spin algorithm
论文作者
论文摘要
局部张量方法是在[Hastings，Arxiv：1905.07047V2] [1]中引入的一类优化算法，作为量子近似优化算法（QAOA）的经典类似物。这些算法将成本函数视为自旋转自由度的哈密顿量，并使用旋转上的本地更新规则模拟系统的放松至低能配置。尽管[1]中的重点是理论上的最差分析，但我们在这里通过基准对Maxcut问题实例进行基准测试实验进行了研究。通过启发式论证，我们提出的公式提出了选择算法的超参数的公式，这些算法与从实验中确定的最佳选择相吻合。我们观察到，局部张量方法与梯度下降密切相关，因为在麦克斯曲子对连续变量的放松下，但在所有测试的情况下，始终优于梯度下降。我们发现通过局部张量方法实现的解决方案与广泛使用的商业优化软件包实现的时间高度不相关。在某些最大情况下，局部张量方法会及时击败商业求解器，以最多两个数量级，反之亦然。最后，我们认为，局部张量方法紧密遵循哈密顿量问题下的离散的，虚构的时间动态。
Local tensor methods are a class of optimization algorithms that was introduced in [Hastings,arXiv:1905.07047v2][1] as a classical analogue of the quantum approximate optimization algorithm (QAOA). These algorithms treat the cost function as a Hamiltonian on spin degrees of freedom and simulate the relaxation of the system to a low energy configuration using local update rules on the spins. Whereas the emphasis in [1] was on theoretical worst-case analysis, we here investigate performance in practice through benchmarking experiments on instances of the MAXCUT problem.Through heuristic arguments we propose formulas for choosing the hyperparameters of the algorithm which are found to be in good agreement with the optimal choices determined from experiment. We observe that the local tensor method is closely related to gradient descent on a relaxation of maxcut to continuous variables, but consistently outperforms gradient descent in all instances tested. We find time to solution achieved by the local tensor method is highly uncorrelated with that achieved by a widely used commercial optimization package; on some MAXCUT instances the local tensor method beats the commercial solver in time to solution by up to two orders of magnitude and vice-versa. Finally, we argue that the local tensor method closely follows discretized, imaginary-time dynamics of the system under the problem Hamiltonian.
