论文标题
注意差距：通过跳到末端实现超螺旋量子加速
Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
论文作者
论文摘要
我们提出了一种量子算法，该算法为几个二进制优化问题的家庭提供了严格的运行时保证，包括二进制不受限制的二进制优化（QUBO），ISING自旋眼镜（$ p $ -spin型号）和$ k $ - $ - $ - 局部约束满意度问题（$ k $ -csp）。我们表明，（a）算法在时间$ o^*（2^{（0.5-c）n}）$中找到最佳解决方案的解决方案，对于$ n $独立的常数$ c $，$ 2^{cn} $优势比Grover的算法优势；或（b）有足够多的低成本解决方案，因此经典的随机猜测会产生$（1-η）$近似值，以在次指定时间中的最佳成本值近似$η$。此外，我们表明，对于$ k $ spin型号的大量随机实例，对于任何令人满意或略微沮丧的$ k $ -csp公式，语句（a）就是这种情况。该算法及其分析在很大程度上受到Hastings的短期路径算法的启发[$ \ textit {Quantum} $ $ \ textbf {2} $（2018）78]。
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems, including Quadratic Unconstrained Binary Optimization (QUBO), Ising spin glasses ($p$-spin model), and $k$-local constraint satisfaction problems ($k$-CSP). We show that either (a) the algorithm finds the optimal solution in time $O^*(2^{(0.5-c)n})$ for an $n$-independent constant $c$, a $2^{cn}$ advantage over Grover's algorithm; or (b) there are sufficiently many low-cost solutions such that classical random guessing produces a $(1-η)$ approximation to the optimal cost value in sub-exponential time for arbitrarily small choice of $η$. Additionally, we show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case. The algorithm and its analysis is largely inspired by Hastings' short-path algorithm [$\textit{Quantum}$ $\textbf{2}$ (2018) 78].
