We present a quantum algorithm for simulating the dynamics of hamiltonians
that are not necessarily sparse. Our algorithm is based on the input model
where the entries of the Hamiltonian are stored in a data stru
我们提出了一种高效的量子算法，用于模拟给定时间 t 内给定稀疏哈密顿量 H 的演化，特别地，当 H 作用于 n 个量子位，每行 / 列最多有恒定数量的非零元素，并且 | H | 受到限制时，我们可以选择任何正整数 k，使得模拟需要 O ((log*n) t^{1+1/2k}) 次访问 H 的矩阵元素。我们证明，除此之外，时间缩放不能显著提高，因为子线性时间缩放不可能。
本文提出了用量子行走模拟黑箱哈密顿量的一般方法。这些技术具有两个主要应用：模拟稀疏哈密顿量和实现黑箱酉操作。我们给出了稀疏 Hamiltonians 常数精度下最好的已知模拟方法，复杂度线性地随着稀疏矩阵的最大非零元素数 D 和演化时间 t 增长，并且我们还研究了给定黑箱描述矩阵元素的任意酉操作实现的任务。