Hastings M B
Microsoft Research, Station Q, Elings Hall, University of California, Santa Barbara, California 93106, USA.
Phys Rev Lett. 2009 Jul 31;103(5):050502. doi: 10.1103/PhysRevLett.103.050502. Epub 2009 Jul 27.
We show that it is possible to use a classical computer to efficiently simulate the adiabatic evolution of a quantum system in one dimension with a constant spectral gap, starting the adiabatic evolution from a known initial product state. The proof relies on a recently proven area law for such systems, implying the existence of a good matrix product representation of the ground state, combined with an appropriate algorithm to update the matrix product state as the Hamiltonian is changed. This implies that adiabatic evolution with such Hamiltonians is not useful for universal quantum computation. Therefore, adiabatic algorithms which are useful for universal quantum computation either require a spectral gap tending to zero or need to be implemented in more than one dimension (we leave open the question of the computational power of adiabatic simulation with a constant gap in more than one dimension).
我们证明，从已知的初始积态开始绝热演化，利用经典计算机可以有效地模拟一维具有恒定谱隙的量子系统的绝热演化。该证明依赖于最近针对此类系统证明的面积定律，这意味着基态存在良好的矩阵乘积表示，再结合一种适当的算法，以便在哈密顿量改变时更新矩阵乘积态。这意味着使用此类哈密顿量的绝热演化对通用量子计算并无用处。因此，对通用量子计算有用的绝热算法要么需要谱隙趋于零，要么需要在多于一维的情况下实现（我们未解决在多于一维且具有恒定谱隙的情况下绝热模拟的计算能力问题）。
