论文标题
量子速度限制的绝热量子算法的下限
Lower bounds for adiabatic quantum algorithms by quantum speed limits
论文作者
论文摘要
我们引入了一个简单的框架，用于估算一系列绝热量子算法的运行时的下限。中央公式包括计算最终哈密顿量相对于初始状态的方差。在检查了某些基于基石电路的量子算法的绝热版本后，该技术应用于具有不确定加速的绝热量子算法。特别是，我们通过分析地获得了绝热算法的下限，以在随机图中查找K-clique。此外，对于特定类别的哈密顿量，基于频谱差距分析的框架与常规方法之间的等价性很简单。
We introduce a simple framework for estimating lower bounds on the runtime of a broad class of adiabatic quantum algorithms. The central formula consists of calculating the variance of the final Hamiltonian with respect to the initial state. After examining adiabatic versions of certain keystone circuit-based quantum algorithms, this technique is applied to adiabatic quantum algorithms with undetermined speedup. In particular, we analytically obtain lower bounds on adiabatic algorithms for finding k-clique in random graphs. Additionally, for a particular class of Hamiltonian, it is straightforward to prove the equivalence between our framework and the conventional approach based on spectral gap analysis.
