论文标题
为什么绝热量子退火不太可能产生加速
Why adiabatic quantum annealing is unlikely to yield speed-up
论文作者
论文摘要
我们研究了与哈密顿的组合优化的量子退火，其中$ h = z h_f + h_0 $其中$ h_f $是对角线，$ h_0 = - | ϕ \ rangle \ langle \ langle ϕ | $是相等的叠加状态投影仪和$ z $ z $退火参数。我们通过分析将最小频谱差距计算为$ \ Mathcal {o}（1/\ sqrt {n}）$，$ n $的状态总数及其位置$ z _*$。我们表明，量子加速需要一个退火时间表，这需要$ z _*$的精确知识，只有知道优化问题的状态密度，才能计算出来。但是，总的来说，状态的密度对计算非常棘手，这使得二次加速对任何实用的组合优化问题都是不可行的。我们认为，这种负结果可能也适用于任何其他实例独立的横向汉密尔顿人，例如$ h_0 = - \ sum_ {i = 1}^nσ_i^x $。
We study quantum annealing for combinatorial optimization with Hamiltonian $H = z H_f + H_0$ where $H_f$ is diagonal, $H_0=-|ϕ\rangle \langle ϕ|$ is the equal superposition state projector and $z$ the annealing parameter. We analytically compute the minimal spectral gap as $\mathcal{O}(1/\sqrt{N})$ with $N$ the total number of states and its location $z_*$. We show that quantum speed-up requires an annealing schedule which demands a precise knowledge of $z_*$, which can be computed only if the density of states of the optimization problem is known. However, in general the density of states is intractable to compute, making quadratic speed-up unfeasible for any practical combinatoric optimization problems. We conjecture that it is likely that this negative result also applies for any other instance independent transverse Hamiltonians such as $H_0 = -\sum_{i=1}^n σ_i^x$.
