Los Alamos National Laboratory, New Mexico 87545, USA.
Phys Rev Lett. 2012 Aug 3;109(5):050501. doi: 10.1103/PhysRevLett.109.050501. Epub 2012 Jul 31.
We study the glued-trees problem from A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. Spielman, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (ACM, San Diego, CA, 2003), p. 59. in the adiabatic model of quantum computing and provide an annealing schedule to solve an oracular problem exponentially faster than classically possible. The Hamiltonians involved in the quantum annealing do not suffer from the so-called sign problem. Unlike the typical scenario, our schedule is efficient even though the minimum energy gap of the Hamiltonians is exponentially small in the problem size. We discuss generalizations based on initial-state randomization to avoid some slowdowns in adiabatic quantum computing due to small gaps.
我们研究了 A. M. Childs、R. Cleve、E. Deotto、E. Farhi、S. Gutmann 和 D. Spielman 在《Proceedings of the 35th Annual ACM Symposium on Theory of Computing》（ACM，圣地亚哥，CA，2003 年）中提出的胶合树问题，该论文研究了在绝热量子计算模型中的应用，并提供了一种退火方案，可以指数级地快于经典计算解决预言问题。参与量子退火的哈密顿量不会受到所谓的符号问题的影响。与典型情况不同的是，即使哈密顿量的最小能量间隙在问题规模上呈指数级小，我们的方案也是高效的。我们还讨论了基于初始状态随机化的推广方案，以避免由于间隙较小而导致的绝热量子计算中的一些减速现象。
