标题： 量子退火对噪声预言机的量子加速敏感性 显示英文标题

标题： Sensitivity of quantum speedup by quantum annealing to a noisy oracle

摘要： 胶合树问题是有史以来唯一一个已知的量子退火提供指数级加速的例子，尽管是部分使用激发态演化，在预言机设置中。对预言机上的噪声，这种加速有多稳健？为了回答这个问题，我们构建了经验性的短程和长程噪声模型，以及破坏或保持光谱反射对称性的噪声模型。我们证明在长程噪声模型下，指数级量子加速仍然存在。然而，我们认为具有等效长程噪声模型的经典算法也相对于无噪声模型表现出指数级加速。在量子设置中，长程噪声能够提升问题的能隙，使得演化从非绝热变为绝热。在经典设置中，长程噪声使行走者直接落在EXIT顶点的概率显著增加。在短程噪声下，指数级加速丢失，但若噪声足够弱，仍保留多项式量子加速。与噪声范围不同，我们发现噪声对光谱对称性的破坏对噪声算法的性能没有显著影响。我们关于长程模型的结果表明，在选择经验性噪声模型时必须小心，以免改变计算问题的本质。我们从短程噪声模型的结果得出结论，胶合树问题中的指数级加速对噪声不鲁棒，但多项式量子加速仍有可能。 显示英文摘要

摘要： The glued-trees problem is the only example known to date for which quantum annealing provides an exponential speedup, albeit by partly using excited state evolution, in an oracular setting. How robust is this speedup to noise on the oracle? To answer this, we construct phenomenological short-range and long-range noise models, and noise models that break or preserve the reflection symmetry of the spectrum. We show that under the long-range noise models an exponential quantum speedup is retained. However, we argue that a classical algorithm with an equivalent long-range noise model also exhibits an exponential speedup over the noiseless model. In the quantum setting the long-range noise is able to lift the spectral gap of the problem so that the evolution changes from diabatic to adiabatic. In the classical setting, long-range noise creates a significant probability of the walker landing directly on the EXIT vertex. Under short-range noise the exponential speedup is lost, but a polynomial quantum speedup is retained for sufficiently weak noise. In contrast to noise range, we find that breaking of spectral symmetry by the noise has no significant impact on the performance of the noisy algorithms. Our results about the long-range models highlight that care must be taken in selecting phenomenological noise models so as not to change the nature of the computational problem. We conclude from the short-range noise model results that the exponential speedup in the glued-trees problem is not robust to noise, but a polynomial quantum speedup is still possible.