论文标题
模拟的量子退火在尖峰哈密顿式上有效
Simulated Quantum Annealing is Efficient on the Spike Hamiltonian
论文作者
论文摘要
在这项工作中，我们研究了一种在Spike Hamiltonian上称为模拟量子退火（SQA）的经典算法的融合，这是一种特定的玩具模型Hamiltonian，用于[FGG02]引入的量子机械隧道。该玩具模型哈密顿式的编码在计算基础上编码了一个简单的位对称成本函数F，并用于在更复杂的优化问题中模仿本地最小值。在先前的工作中[CH16]表明，SQA在质量保证措施所做的大部分尖峰状态下在多项式时间内运行，这表明通过隧道进行了反对指数加速的证据。在本文中，我们将它们的分析扩展到了尖峰汉密尔顿的剩余的多项式状态，以表明质量保证在这个玩具模型家族中对SQA没有指数的速度。
In this work we study the convergence of a classical algorithm called Simulated Quantum Annealing (SQA) on the Spike Hamiltonian, a specific toy model Hamiltonian for quantum-mechanical tunneling introduced by [FGG02]. This toy model Hamiltonian encodes a simple bit-symmetric cost function f in the computational basis, and is used to emulate local minima in more complex optimization problems. In previous work [CH16] showed that SQA runs in polynomial time in much of the regime of spikes that QA does, pointing to evidence against an exponential speedup through tunneling. In this paper we extend their analysis to the remaining polynomial regime of energy gaps of the spike Hamiltonian, to show that indeed QA presents no exponential speedup with respect to SQA on this family of toy models.
