论文标题
（子）绝热量子计算的指数优势，没有任何符号问题
(Sub)Exponential advantage of adiabatic quantum computation with no sign problem
论文作者
论文摘要
我们证明了（子）指数量子加速的可能性，该量子加速通过遵循没有符号问题的巨大哈密顿量的绝热路径的量子算法。这加强了黑斯廷斯最近证明的超级分离分离。表现出这种速度的哈密顿量来自一个无方向图的邻接矩阵，我们可以将绝热进化视为有效的$ \ MATHCAL {O}（\ Mathrm {poly}（poly}（n））$ - 时间量子量子算法，用于在图中找到特定的“ exit” ext'顶点“ exit” ext fived fived fish fish fish fish fish fish fish fish fish fish the oftrance'oftrance'retrance'vertex vertex。另一方面，我们表明，如果通过邻接列表甲骨文给出该图，则没有经典算法可以使用最多使用$ \ exp（n^δ）$查询的概率大于$ \ exp（-n^δ）$的“退出”，以$δ= = = \ frac15-o（1）$。我们的图形结构与Childs等人的“焊接树”结构有些相似，但是使用Hastings的其他想法来实现光谱差距和短暂的绝热路径。
We demonstrate the possibility of (sub)exponential quantum speedup via a quantum algorithm that follows an adiabatic path of a gapped Hamiltonian with no sign problem. This strengthens the superpolynomial separation recently proved by Hastings. The Hamiltonian that exhibits this speed-up comes from the adjacency matrix of an undirected graph, and we can view the adiabatic evolution as an efficient $\mathcal{O}(\mathrm{poly}(n))$-time quantum algorithm for finding a specific "EXIT" vertex in the graph given the "ENTRANCE" vertex. On the other hand we show that if the graph is given via an adjacency-list oracle, there is no classical algorithm that finds the "EXIT" with probability greater than $\exp(-n^δ)$ using at most $\exp(n^δ)$ queries for $δ= \frac15 - o(1)$. Our construction of the graph is somewhat similar to the "welded-trees" construction of Childs et al., but uses additional ideas of Hastings for achieving a spectral gap and a short adiabatic path.
